/usr/share/axiom-20170501/src/algebra/HB.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | )abbrev package HB HallBasis
++ Author : Larry Lambe
++ Date Created : August 1988
++ Date Last Updated : March 9 1990
++ Description:
++ Generate a basis for the free Lie algebra on n
++ generators over a ring R with identity up to basic commutators
++ of length c using the algorithm of P. Hall as given in Serre's
++ book Lie Groups -- Lie Algebras
HallBasis() : SIG == CODE where
B ==> Boolean
I ==> Integer
NNI ==> NonNegativeInteger
VI ==> Vector Integer
VLI ==> Vector List Integer
SIG ==> with
lfunc : (I,I) -> I
++ lfunc(d,n) computes the rank of the nth factor in the
++ lower central series of the free d-generated free Lie
++ algebra; This rank is d if n = 1 and binom(d,2) if
++ n = 2
inHallBasis? : (I,I,I,I) -> B
++ inHallBasis?(numberOfGens, leftCandidate, rightCandidate, left)
++ tests to see if a new element should be added to the P. Hall
++ basis being constructed.
++ The list \spad{[leftCandidate,wt,rightCandidate]}
++ is included in the basis if in the unique factorization of
++ rightCandidate, we have left factor leftOfRight, and
++ leftOfRight <= leftCandidate
generate : (NNI,NNI) -> VLI
++ generate(numberOfGens, maximalWeight) generates a vector of
++ elements of the form [left,weight,right] which represents a
++ P. Hall basis element for the free lie algebra on numberOfGens
++ generators. We only generate those basis elements of weight
++ less than or equal to maximalWeight
CODE ==> add
lfunc(d,n) ==
n < 0 => 0
n = 0 => 1
n = 1 => d
sum:I := 0
m:I
for m in 1..(n-1) repeat
if n rem m = 0 then
sum := sum + m * lfunc(d,m)
res := (d**(n::NNI) - sum) quo n
inHallBasis?(n,i,j,l) ==
i >= j => false
j <= n => true
l <= i => true
false
generate(n:NNI,c:NNI) ==
gens:=n
maxweight:=c
siz:I := 0
for i in 1 .. maxweight repeat siz := siz + lfunc(gens,i)
v:VLI:= new(siz::NNI,[])
for i in 1..gens repeat v(i) := [0, 1, i]
firstindex:VI := new(maxweight::NNI,0)
wt:I := 1
firstindex(1) := 1
numComms:I := gens
newNumComms:I := numComms
done:B := false
while not done repeat
wt := wt + 1
if wt > maxweight then done := true
else
firstindex(wt) := newNumComms + 1
leftIndex := 1
-- cW == complimentaryWeight
cW:I := wt - 1
while (leftIndex <= numComms) and (v(leftIndex).2 <= cW) repeat
for rightIndex in firstindex(cW)..(firstindex(cW+1) - 1) repeat
if inHallBasis?(gens,leftIndex,rightIndex,v(rightIndex).1) then
newNumComms := newNumComms + 1
v(newNumComms) := [leftIndex,wt,rightIndex]
leftIndex := leftIndex + 1
cW := wt - v(leftIndex).2
numComms := newNumComms
v
|