phb

 

  
Purpose 		 
Generate a Philip Hall basis.




Syntax 		 
B:=phb(m,k);




Description 		 

This function constructs a list containing the Philip Hall basis (PHB)
for a nilpotent Lie algebra of degree $k$ generated by $m$ generators.
The elements in the PHB are elements of the Lie algebra selected in
way such that the dependencies between brackets, imposed by the
anti-symmetry property and the Jacobi identity, are taken into
account.





Arguments 		 
$m$  Number of Lie algebra generators.


 		 $k$ $\parbox{0.64\textwidth}{Order of nilpotency,
 i.e. brackets of length k+1 and higher are equal to zero.}$




Examples 		 

Construct a Philip Hall basis for a nilpotent algebra of order 4
 generated by 3 vector fields.
> B:=phb(3,4);
B:=[f0~, f1~, f2~, f0~ &* f1~, f0~ &* f2~, f1~ &* f2~,
    f0~ &* (f0~ &* f1~), f0~ &* (f0~ &* f2~), f1~ &* (f0~ &* f1~),
    f1~ &* (f0~ &* f2~), f1~ &* (f1~ &* f2~), f2~ &* (f0~ &* f1~),
    f2~ &* (f0~ &* f2~), f2~ &* (f1~ &* f2~),
    (f0~ &* f1~) &* (f0~ &* f2~), (f0~ &* f1~) &* (f1~ &* f2~),
    (f0~ &* f2~) &* (f1~ &* f2~), f0~ &* (f0~ &* (f0~ &* f1~)),
    f0~ &* (f0~ &* (f0~ &* f2~)), f1~ &* (f0~ &* (f0~ &* f1~)),
    f1~ &* (f0~ &* (f0~ &* f2~)), f1~ &* (f1~ &* (f0~ &* f1~)),
    f1~ &* (f1~ &* (f0~ &* f2~)), f1~ &* (f1~ &* (f1~ &* f2~)),
    f2~ &* (f0~ &* (f0~ &* f1~)), f2~ &* (f0~ &* (f0~ &* f2~)),
    f2~ &* (f1~ &* (f0~ &* f1~)), f2~ &* (f1~ &* (f0~ &* f2~)),
    f2~ &* (f1~ &* (f1~ &* f2~)), f2~ &* (f2~ &* (f0~ &* f1~)),
    f2~ &* (f2~ &* (f0~ &* f2~)), f2~ &* (f2~ &* (f1~ &* f2~))]





Notes 		
 
This function also declares the symbol for the Lie product operator
denoted by &* if it was not previously assigned. This is only
to ensure that &* and its properties (see Loading LTP
in section 2.3 have been assigned in case it was
manually removed.   The &* operator is created by default at
startup when the package is loaded.





Limitations 		 

There aren't any known limitations, besides the normal limitations
imposed by the memory of the machine.





See Also 		 phbize.




Algorithm 		

The Philip Hall Basis


Due to the antisymmetry property and the Jacobi identity not all the
elements of the Lie algebra $\mathcal{L}(g_1,\ldots, g_m)$ generated
by $g_1,\ldots, g_m$ are linearly independent.  One possible method
for constructing a basis which takes into account the dependencies
imposed by the mentioned properties is to list all the
generators $g_1,\ldots, g_m$ and select some of their Lie products
according to the Philip Hall procedure described
next [32].


Denote by $B$ the basis, and let $B_i$ be the $i$-th element
in the basis.  Define the length $l(G)$ of a Lie product $G$ as the number of
generators in the expansion for $G$ or, alternatively in a recursive
way:




$$l(g_i) = 1\hspace{2cm} i=1,\ldots,m$$ 
(34)
$$l([G,H]) = l(G)+l(H)$$ 
(35)


where $G$ and $H$ are Lie products.


Then a Philip Hall basis is an ordered set of Lie products $\{B_i\}$
satisfying:


$g_i \in B,\ i=1,\ldots, m$

If $l(B_i)<l(B_j)$ then $B_i<B_j$

$[B_i, B_j] \in B$ if and only if
   


$B_i, B_j \in B$ and $B_i<B_j$ and

either $B_j=g_k$ for some $k$ or $B_j=[B_p, B_q]$ with $B_p,
B_q \in B$ and $B_p\leq B_i$.
   






For proofs that a Philip Hall basis is indeed a basis for the Lie
algebra generated by $g_1,\ldots, g_m$ the reader is referred to:


J-P. Serre. Lie Algebras and Lie groups.  W. A. Benjamin, New York,
1965.


M. Hall.  The Theory of Groups. Macmillan, 1959.


A Philip Hall basis which is nilpotent of order $k$ can also be
constructed from the above definition by simply constructing all the
Lie products that satisfy the properties in the above definition and
have length not greater than $k$.

  
Implementation Notes		





The implementation of the algorithm is illustrated in the flow chart of
Figs. .  For further details and
remarks on the implementation the reader is referred to the source
code.


From a practical perspective, the basis B can be built in such
a way that only condition 3 needs to be checked, since condition 1
must be assumed true for all initial generators and 2 may be
satisfied by performing the multiplications in an orderly manner, as
briefly described next.


Condition 3 is implemented within the dashed block labeled ``Create
bracket $[B_i,B_j]$'', shown in Fig. 5.


The bracketing procedure (i.e. the procedure for generating new Lie
products or brackets) can be though of as a breeding process.  We must
distinguish between to groups per ``breeding season'' (iteration), the
offspring and the parents.


On the first iteration the generators are treated as offspring
and are crossed between them.  On the second iteration,
the offspring are called parents (since they will be crossed they will
become parents), and their offspring are the new offspring.  Parents
are crossed only with their offspring and not between them, since this
happened in the previous iteration.  While offspring are crossed between
them and also their parents to cover all possible combinations.  All
the newborns are now called offspring and the ones that were offspring
are now in the group of parents.  And life goes on...


Offspring are ``cross-fertilized'' as shown in Fig. 6.2.

  
		
Figure 3:
Lie bracketing tree.


    
 







  

  
 		

Note that the [B,C], [C,A] and [B,A] are not valid offspring since
they violate condition 2, assuming a lexicographical order is followed,
i.e. A, B, C, are respectively the first, second and third generators.


Now there are two groups: parents A, B, C and offspring [A,B],
[A,C], [B,C], denoted AB, AC and BC for short.  Offspring will
reproduce again as graphically described in the above figure, but also
they will be crossed with their parents.  All parents are crossed with
all offspring, in the following way:
  AxAB AxAC AxBC
  BxAB BxAC BxBC
  CxAB CxAC CxBC

Where 'x' stands for crossed with, i.e. represents the Lie product
operator.  Note that some of the crossings must be eliminated by rule
3, namely AxBC.

In the flow chart of Figs. 4-5, $b$ denotes
the bracketing iteration (breeding season), $g_old$ is the number of
brackets that have been multiplied (crossed) at least once, $g_tot$ is
the number the total number of brackets including parents and
offspring updated at the end of the iteration.  Note that
$g_tot$ is note incremented as the breeding occurs since its value is
necessary to close loop L3, in Fig. 5, to keep track of
the new brackets the variable $g_acum$ is used, instead, and its value
will be passed to $g_tot$ once the loop L3 is completed. The index $i$
points to each element in the initial population, and is associated
with the first term in the bracket $[B_i,B_j]$, while the index $j$
associated with the second term in the bracket is set to start at the
value of $j_min$ according to whether the the crossings will be done
between the offspring only ($j_min=i+1$) or between the parents and the
offspring ($j_min=g_old+1$).

Figure 4: Flow chart for the phb algorithm (contd. on Fig. 5).

Figure 5: Flow chart for the phb algorithm (contd. from Fig. 4).