phbize

  
Purpose 		

Transform any Lie bracket to a bracket or linear combination of
brackets in the PHB.  If the input Lie bracket is already an element
of the PHB, then it is returned unchanged.





Syntax 		 
xr:=phbize(x,B);




Description 		 

The function phbize($x,B$) transforms the
Lie bracket $x$ to a corresponding bracket or linear combination of
brackets in the PHB, if $x$ is not already in the PHB which must be passed
in the second argument $B$.  It is assumed that $x$
is a pure bracket , i.e. the scalar parts have
been removed (see the function simpLB, which allows to obtain
the pure bracket as explained there).



NOTE: This function accepts arguments $x$ of order higher than
  the degree of nilpotency of the Lie algebra, and which might exceed
  the degree of the highest order brackets in the basis. If the order
  of the term $x$ exceeds the degree of nilpotency, but it is composed
  by the product of two elements in the PHB, the result returned will
  be correct.  However, for more complicated brackets the result will
  be a partial simplification, not necessarily and element of the PHB,
  and thus the result  must be interpreted with care.





Arguments 		 
$x$  Some pure Lie bracket.


 		 $B$ $\parbox{0.64\textwidth}{Philip Hall basis}$




Examples 		

The following examples consider the PHB B shown in the
example for the command phb on page .
> phbize(f0&*(f1&*f0),B);
-(f0~ &* (f0~ &* f1~))

The six combinations of 3-generator brackets and their equivalences
in terms of PHB elements are calculated below.  Notice the implicit
use of the anti-commutativity law and Jacobi identity, the latter
relating the first three or last three brackets.
> phbize(f0&*(f1&*f2),B);phbize(f2&*(f0&*f1),B);phbize(f1&*(f2&*f0),B);
> phbize(f0&*(f2&*f1),B);phbize(f2&*(f1&*f0),B);phbize(f1&*(f0&*f2),B);
           -(f2~ &* (f0~ &* f1~)) + (f1~ &* (f0~ &* f2~))
                          f2~ &* (f0~ &* f1~)
                        -(f1~ &* (f0~ &* f2~))
            (f2~ &* (f0~ &* f1~)) - (f1~ &* (f0~ &* f2~))
                        -(f2~ &* (f0~ &* f1~))
                          f1~ &* (f0~ &* f2~)





Algorithm 		 

This routine considers implicitly both the anti-symmetry property and
the Jacobi identity, through the verification of the conditions for
the construction of the PHB (cf. PHB algorithm ),
since the conversion of any bracket to an element, or a linear
combination of the elements, in the PHB must result in an bracket that
complies with the rules used for the construction of the PHB.  As
previously mentioned, the rules for the construction of the PHB take
into account the anti-symmetry property and the Jacobi identity to
select only the independent brackets from all possible combinations.


So the main steps of the phbize algorithm consist in verifying
which rule or rules are violated by the Lie bracket, if it is not
already in the PHB, and making the appropriate correction so that the
condition is satisfied by the resulting bracket.  Assuming the Lie
any Lie bracket $x$ can be decomposed into its left and right operands
by respectively applying the functions $lo$ and $ro$ to $x$,
i.e. $lo(x)$ and $ro(x$ return the left and right operand of $x$, 
respectively. And assuming also that the operations $lo(\cdot)$ and
$ro(\cdot)$ can be composed iteratively to obtain, say the right
operand of the left operand $ro(lo(x))$, then the main steps of the
phbize procedure in strict order can be summarized as: 


Verify $x \in B$.

Verify $lo(x) \neq ro(x)$.

Verify $lo(x) \in B$ and $ro(x) \in B$.

Verify $len(lo(x)) < len(ro(x)) \Leftrightarrow pos(lo(x),B) <
 pos(ro(x),B)$.

Verify $pos\left( lo(ro(x))\right ) \leq pos \left (lo(x)\right )$. 

 
Where the functions $len(x)$ and $pos(x,B)$ return the length
(i.e. the number of operands) of the bracket $x$ and the position of
$x$ in the basis $B$, respectively.


The above rules are related to the Lie bracket properties and the
rules for the construction of the PHB.  Particular connections can be
made between the above conditions and the Lie bracket properties or
the conditions in the phb algorithm (cf. p. ).
This relations are summarized in the Table 6.3 below.

  
		
Table 3:
Connections between phbize conditions, phb construction rules and the Lie bracket properties.



phbize condition
phb condition
Lie product
property

1
1
-

2
-
anti-symmetry

$3 \wedge 4$
3.a
anti-symmetry

4
2
anti-symmetry

5
3.b
Jacobi identity




$\parbox{0.9\textwidth}{

}$

  
		

All the conditions in the above table associated with the
anti-symmetry property should imply the reordering (swapping) of the
operands of $x$, with the exception of the phbize condition 2,
which should return zero, since by the anti-symmetry property
$[a,b]=[b,a]\Leftrightarrow [a,b]+[a,b]=0 \Rightarrow [a,b]=[b,a]=0$
only if $a=b$.  In the case the bracket $x$ does not satisfy the
condition associated with the Jacobi identity, then phbize
should return the sum of the two other terms in the Jacobi identity.


show the flow chart
illustrating the algorithm for the application for the verification of
the above rules and the transformation of $x$ into an element in the
PHB $B$.


The functions $len(x)$ and $pos(x,B)$ mentioned above, have been
implemented and called bracketlen and posxinphb.  These
two functions are available to the user, though their immediate use
does not seem strictly necessary.  Both, bracketlen and
posxinphb are described in the next subsections.





Remarks 		 

At this point it is worth to make some remarks on how a procedure to
construct a basis for some Lie algebra, such as the one described to
construct the Philip Hall basis can be devised.


The first observation is the obvious dependency imposed by
anti-symmetry property between a bracket and its commuted product.  By
taking into account this simply property, we are basically prescribing
that we either consider $[f,g]$ or $-[g,f]$ but not both, so selecting
the first bracket leads to establishing some order, in this case a
lexicographical order.  Thus, the ordered basis condition 1 for
phb is somewhat implicit due to the anti-symmetry, which also
leads to condition 2.


Next, if three ordered generators $f, g, h$ are considered, it is not
difficult to see that there are 6 possible ways in which their product
can occur.  This 6 ordered triples are fgh, fhg, hfg, hgf, ghf and
gfh.  Considering these combinations of $f, g$ and $h$, the Jacobi
identity can be written only in the next two ways:



$$\begin{array}{ccc}
\hspace{1em}[f,[g,h]]&+[h,[f,g]]&+[g,[h,f]]=0\...
...\Updownarrow & \Updownarrow\\  
-[f,[h,g]]&-[h,[g,f]]&-[g,[f,h]]=0
\end{array}~$$ 
(36)


Note that the second equation simply results from the first one by
applying the anti-symmetry property to the right operand of each Lie
product.  Note also that other forms of the Jacobi identity in which
the left operand has length 2 are discarded since this violate the
ordering rule 2 ($pos(lo(x),B)<len(ro(x),B)$).


So basically, all what is needed is to select the dependent and
independent terms in the above Jacobi identity.  The independent terms
must belong to the basis $B$ and therefore they must already be such
that they satisfy the ordering and the anti-symmetry properties.


Checking the terms in (36) it is possible to identify those
that do not satisfy the ordering condition 4, and the condition 5, as
indicated in the equation (37), below.  All the terms that
do not satisfy 4 can easily be brought to a form that is the the basis
$B$ by simply swapping the elements in the right operand and making a
sign correction.  The exception to the last statement is the first
term in the second equation of (37) which if corrected by
swapping the operands of the right operand, then it violates condition
5 since $pos(lo(ro([f,[g,h]])))=pos(g)$ is greater than
$pos(lo([f,[g,h]]))=pos(f)$.  Thus, the first term in (37)
is the dependent term, since it cannot be brought into a form that is
in the basis $B$ by simply swapping operands in the right operand and
therefore it will have to be expressed as the sum of the two terms
that have been marked with a $\surd$ in (37), which are
elements of the basis $B$. 





		






$$\begin{array}{ccc}
\hspace{1em}
[\overbrace{f,[g}^{\times 5},h]] ...
...-[h,[\overbrace{g,f}^{\times 4}]] &
-\stackrel{\surd}{[g,[f,h]]}=0
\end{array}~$$ 
(37)


So now the final equation for the dependent Lie product in terms of the
independent basis brackets as




$$[f,[g,h]]:=-[h,[f,g]]+[g,[f,h]]$$ 
(38)


which for an indeterminate bracket $x$ can be written in the general
form




$${[lo(x),[lo(ro(x)),ro(ro(x))]]:=}\hspace{2cm}$$
$$-[ro(ro(x)),[lo(x),lo(ro(x))]]$$ 
(39)
$$+[lo(ro(x)),[lo(x),ro(ro(x))]]$$


as also shown in the last process box of the flow chart in
Fig. 7.





Sign removal 		
 
The sign removal is not a function, but rather a process required to
deal with brackets of the form $-x$, since the basis PHB $B$ only
contains the positive version of the brackets.


Suppose that $x$ is indeed an element of $B$, then $-x$ does not need
any processing, since it is evidently a bracket expressed in terms of
$x \in B$, however from an implementation standpoint, checking the
membership of $-x$ in $B$ fails to return a positive answer, and the
the program must be adapted to handle this case.  This can easily be
achieved by first checking if the symbolic variable has a minus sign
in front; if so, then the sign must be stored and the membership to $B$ of
the negated bracket must be checked instead.  Once some possible
processes have been performed on the variable, the result is negated
previous been returned to recover the sign of the original bracket
passed as input to the phbize function (as well as some other
functions of the LTP).  This process of sign removal and restoration
is shown in the flow chart of Fig. 10.





See Also 		 
posxinphb(x), bracketlen(x)

Figure 6: Flow chart for the phbize algorithm (contd. on Fig. 7).

Figure 7: Flow chart for the phbize algorithm (contd. from Fig. 6).

Figure 8: Flow chart for the phbize algorithm (contd. from Fig. 7).

Figure 9: Flow chart for the phbize algorithm (contd. from Fig. 7).

Figure 10: Flow chart for the sign removal procedure.