diff options
Diffstat (limited to 'src/algebra')
-rw-r--r-- | src/algebra/cycles.spad.pamphlet | 55 | ||||
-rw-r--r-- | src/algebra/irsn.spad.pamphlet | 43 | ||||
-rw-r--r-- | src/algebra/partperm.spad.pamphlet | 29 | ||||
-rw-r--r-- | src/algebra/perm.spad.pamphlet | 8 | ||||
-rw-r--r-- | src/algebra/permgrps.spad.pamphlet | 2 | ||||
-rw-r--r-- | src/algebra/prtition.spad.pamphlet | 26 | ||||
-rw-r--r-- | src/algebra/sgcf.spad.pamphlet | 19 |
7 files changed, 93 insertions, 89 deletions
diff --git a/src/algebra/cycles.spad.pamphlet b/src/algebra/cycles.spad.pamphlet index b8bf2e16..c2941dd3 100644 --- a/src/algebra/cycles.spad.pamphlet +++ b/src/algebra/cycles.spad.pamphlet @@ -33,35 +33,36 @@ CycleIndicators: Exports == Implementation where RN ==> Fraction Integer FR ==> Factored Integer macro NNI == NonNegativeInteger + macro PI == PositiveInteger Exports ==> with - complete: NNI -> SPOL RN + complete: PI -> SPOL RN ++\spad{complete n} is the \spad{n} th complete homogeneous ++ symmetric function expressed in terms of power sums. ++ Alternatively it is the cycle index of the symmetric ++ group of degree n. - powerSum: NNI -> SPOL RN + powerSum: PI -> SPOL RN ++\spad{powerSum n} is the \spad{n} th power sum symmetric ++ function. - elementary: NNI -> SPOL RN + elementary: PI -> SPOL RN ++\spad{elementary n} is the \spad{n} th elementary symmetric ++ function expressed in terms of power sums. - alternating: NNI -> SPOL RN + alternating: PI -> SPOL RN ++\spad{alternating n} is the cycle index of the ++ alternating group of degree n. - cyclic: NNI -> SPOL RN --cyclic group + cyclic: PI -> SPOL RN --cyclic group ++\spad{cyclic n} is the cycle index of the ++ cyclic group of degree n. - dihedral: NNI -> SPOL RN --dihedral group + dihedral: PI -> SPOL RN --dihedral group ++\spad{dihedral n} is the cycle index of the ++ dihedral group of degree n. - graphs: NNI -> SPOL RN + graphs: PI -> SPOL RN ++\spad{graphs n} is the cycle index of the group induced on ++ the edges of a graph by applying the symmetric function to the ++ n nodes. @@ -83,7 +84,7 @@ CycleIndicators: Exports == Implementation where ++ of the two groups whose cycle indices are \spad{s1} and ++ \spad{s2}. - SFunction:L I -> SPOL RN + SFunction:L PI -> SPOL RN ++\spad{SFunction(li)} is the S-function of the partition \spad{li} ++ expressed in terms of power sum symmetric functions. @@ -99,24 +100,24 @@ CycleIndicators: Exports == Implementation where trm: PTN -> SPOL RN trm pt == monomial(inv(pdct(pt) :: RN),pt) - list: Stream L I -> L L I + list: Stream L PI -> L L PI list st == entries complete st complete i == i=0 => 1 - +/[trm(partition pt) for pt in list(partitions i)] + +/[trm partition pt for pt in list partitions i] - even?: L I -> B + even?: L PI -> B even? li == even?( #([i for i in li | even? i])) alternating i == - 2 * _+/[trm(partition li) for li in list(partitions i) | even? li] + 2 * _+/[trm partition li for li in list partitions i | even? li] elementary i == i=0 => 1 - +/[(spol := trm(partition pt); even? pt => spol; -spol) - for pt in list(partitions i)] + +/[(spol := trm partition pt; even? pt => spol; -spol) + for pt in list partitions i] divisors: I -> L I divisors n == @@ -125,23 +126,23 @@ CycleIndicators: Exports == Implementation where [[a.factor**j for j in 1..a.exponent] for a in b]); if #(b) = 1 then c else concat(n,c) - ss: (I,I) -> SPOL RN + ss: (PI,I) -> SPOL RN ss(n,m) == - li : L I := [n for j in 1..m] + li : L PI := [n for j in 1..m] monomial(1,partition li) powerSum n == ss(n,1) cyclic n == n = 1 => powerSum 1 - +/[(eulerPhi(i) / n) * ss(i,numer(n/i)) for i in divisors n] + +/[(eulerPhi(i) / n) * ss(i::PI,numer(n/i)) for i in divisors n] dihedral n == k := n quo 2 odd? n => (1/2) * cyclic n + (1/2) * ss(2,k) * powerSum 1 (1/2) * cyclic n + (1/4) * ss(2,k) + (1/4) * ss(2,k-1) * ss(1,2) - trm2: L I -> SPOL RN + trm2: L PI -> SPOL RN trm2 li == lli := powers(partition li)$PTN xx := 1/(pdct partition li) @@ -151,12 +152,12 @@ CycleIndicators: Exports == Implementation where k := ll0 quo 2 c := odd? ll0 => ss(ll0,ll1 * k) - ss(k,ll1) * ss(ll0,ll1 * (k - 1)) + ss(k::PI,ll1) * ss(ll0,ll1 * (k - 1)) c := c * ss(ll0,ll0 * ((ll1*(ll1 - 1)) quo 2)) prod2 : SPOL RN := 1 for r in lli | first(r) < ll0 repeat r0 := first r; r1 := second r - prod2 := ss(lcm(r0,ll0),gcd(r0,ll0) * r1 * ll1) * prod2 + prod2 := ss(lcm(r0,ll0)::PI,gcd(r0,ll0) * r1 * ll1) * prod2 prod := c * prod2 * prod xx * prod @@ -180,24 +181,24 @@ CycleIndicators: Exports == Implementation where cap(spol1,spol2) == eval cup(spol1,spol2) - mtpol: (I,SPOL RN) -> SPOL RN + mtpol: (PI,SPOL RN) -> SPOL RN mtpol(n,spol)== zero? spol => 0 - deg := partition [n*k for k in (degree spol)::L(I)] + deg := partition [n*k for k in (degree spol)::L(PI)] monomial(leadingCoefficient spol,deg) + mtpol(n,reductum spol) - evspol: ((I -> SPOL RN),SPOL RN) -> SPOL RN + evspol: ((PI -> SPOL RN),SPOL RN) -> SPOL RN evspol(fn2,spol) == zero? spol => 0 lc := leadingCoefficient spol - prod := */[fn2 i for i in (degree spol)::L(I)] + prod := */[fn2 i for i in (degree spol)::L(PI)] lc * prod + evspol(fn2,reductum spol) wreath(spol1,spol2) == evspol(mtpol(#1,spol2),spol1) SFunction li== a:Matrix SPOL RN := - matrix [[complete((k -j+i)::NNI) for k in li for j in 1..#li] + matrix [[complete((k -j+i)::PI) for k in li for j in 1..#li] for i in 1..#li] determinant a @@ -210,7 +211,7 @@ CycleIndicators: Exports == Implementation where #li1 < #li2 => error "skewSFunction: partition1 does not include partition2" li2:=roundup (li1,li2) - a:Matrix SPOL RN:=matrix [[complete((k-li2.i-j+i)::NNI) + a:Matrix SPOL RN:=matrix [[complete((k-li2.i-j+i)::PI) for k in li1 for j in 1..#li1] for i in 1..#li1] determinant a @@ -252,7 +253,7 @@ EvaluateCycleIndicators(F):T==C where pt:PTN spol:SPOL RN i:I - evp(fn, pt)== */[fn i for i in pt::(L I)] + evp(fn, pt)== */[fn i for i in pt::L(PositiveInteger)] eval(fn,spol)== if spol=0 diff --git a/src/algebra/irsn.spad.pamphlet b/src/algebra/irsn.spad.pamphlet index 4cde0675..95d9a257 100644 --- a/src/algebra/irsn.spad.pamphlet +++ b/src/algebra/irsn.spad.pamphlet @@ -55,27 +55,28 @@ IrrRepSymNatPackage(): public == private where ICF ==> IntegerCombinatoricFunctions Integer PP ==> PartitionsAndPermutations PERM ==> Permutation + macro PI == PositiveInteger public ==> with - dimensionOfIrreducibleRepresentation : L I -> NNI + dimensionOfIrreducibleRepresentation : L PI -> NNI ++ dimensionOfIrreducibleRepresentation(lambda) is the dimension ++ of the ordinary irreducible representation of the symmetric group ++ corresponding to {\em lambda}. ++ Note: the Robinson-Thrall hook formula is implemented. - irreducibleRepresentation : (L I, PERM I) -> M I + irreducibleRepresentation : (L PI, PERM I) -> M I ++ irreducibleRepresentation(lambda,pi) is the irreducible representation ++ corresponding to partition {\em lambda} in Young's natural form of the ++ permutation {\em pi} in the symmetric group, whose elements permute ++ {\em {1,2,...,n}}. - irreducibleRepresentation : L I -> L M I + irreducibleRepresentation : L PI -> L M I ++ irreducibleRepresentation(lambda) is the list of the two ++ irreducible representations corresponding to the partition {\em lambda} ++ in Young's natural form for the following two generators ++ of the symmetric group, whose elements permute ++ {\em {1,2,...,n}}, namely {\em (1 2)} (2-cycle) and ++ {\em (1 2 ... n)} (n-cycle). - irreducibleRepresentation : (L I, L PERM I) -> L M I + irreducibleRepresentation : (L PI, L PERM I) -> L M I ++ irreducibleRepresentation(lambda,listOfPerm) is the list of the ++ irreducible representations corresponding to {\em lambda} ++ in Young's natural form for the list of permutations @@ -84,10 +85,10 @@ IrrRepSymNatPackage(): public == private where private ==> add -- local variables - oldlambda : L I := nil$(L I) + oldlambda : L PI := nil$L(PI) flambda : NNI := 0 -- dimension of the irreducible repr. younglist : L M I := nil$(L M I) -- list of all standard tableaus - lprime : L I := nil$(L I) -- conjugated partition of lambda + lprime : L PI := nil$L(PI) -- conjugated partition of lambda n : NNI := 0 -- concerning symmetric group S_n rows : NNI := 0 -- # of rows of standard tableau columns : NNI := 0 -- # of columns of standard tableau @@ -100,7 +101,7 @@ IrrRepSymNatPackage(): public == private where -- (signum(k,l,id))_1 <= k,l <= flambda, where id -- denotes the identity permutation - alreadyComputed? : L I -> Void + alreadyComputed? : L PI -> Void -- test if the last calling of an exported function concerns -- the same partition lambda as the previous call @@ -119,9 +120,9 @@ IrrRepSymNatPackage(): public == private where -- otherwise -- signum(k,l,pi) = 0. - sumPartition : L I -> NNI - -- checks if lambda is a proper partition and results in - -- the sum of the entries + -- checks if lambda is a proper partition and results in + -- the sum of the entries + sumPartition : L PI -> NNI testPermutation : L I -> NNI -- testPermutation(pi) checks if pi is an element of S_n, @@ -157,12 +158,12 @@ IrrRepSymNatPackage(): public == private where alreadyComputed?(lambda) == - if not(lambda = oldlambda) then + if lambda ~= oldlambda then oldlambda := lambda lprime := conjugate(lambda)$PP - rows := (first(lprime)$(L I))::NNI - columns := (first(lambda)$(L I))::NNI - n := (+/lambda)::NNI + rows := first(lprime)$L(PI) + columns := first(lambda)$L(PI) + n := +/lambda younglist := listYoungTableaus(lambda)$SGCF flambda := #younglist aIdInverse() -- side effect: creates actual aId @@ -240,14 +241,14 @@ IrrRepSymNatPackage(): public == private where sumPartition(lambda) == ok : B := true prev : I := first lambda - sum : I := 0 + sum : NNI := 0 for x in lambda repeat sum := sum + x ok := ok and (prev >= x) prev := x if not ok then error("No proper partition ") - sum::NNI + sum testPermutation(pi : L I) : NNI == @@ -273,7 +274,7 @@ IrrRepSymNatPackage(): public == private where dimensionOfIrreducibleRepresentation(lambda) == nn : I := sumPartition(lambda)::I --also checks whether lambda dd : I := 1 --is a partition - lambdaprime : L I := conjugate(lambda)$PP + lambdaprime := conjugate(lambda)$PP -- run through all rows of the Youngtableau corr. to lambda for i in 1..lambdaprime.1 repeat -- run through all nodes in row i of the Youngtableau @@ -284,7 +285,7 @@ IrrRepSymNatPackage(): public == private where (factorial(nn)$ICF quo dd)::NNI - irreducibleRepresentation(lambda:(L I),pi:(PERM I)) == + irreducibleRepresentation(lambda: L PI,pi: PERM I) == nn : NNI := sumPartition(lambda) alreadyComputed?(lambda) piList : L I := listPermutation pi @@ -298,8 +299,8 @@ IrrRepSymNatPackage(): public == private where irreducibleRepresentation(lambda) == - listperm : L PERM I := nil$(L PERM I) - li : L I := nil$(L I) + listperm : L PERM I := nil$L(PERM I) + li : L I := nil$L(I) sumPartition(lambda) alreadyComputed?(lambda) listperm := @@ -314,7 +315,7 @@ IrrRepSymNatPackage(): public == private where irreducibleRepresentation(lambda,listperm) - irreducibleRepresentation(lambda:(L I),listperm:(L PERM I)) == + irreducibleRepresentation(lambda: L PI,listperm: L PERM I) == sumPartition(lambda) alreadyComputed?(lambda) [irreducibleRepresentation(lambda, pi) for pi in listperm] diff --git a/src/algebra/partperm.spad.pamphlet b/src/algebra/partperm.spad.pamphlet index b657fa3a..d4b23b3a 100644 --- a/src/algebra/partperm.spad.pamphlet +++ b/src/algebra/partperm.spad.pamphlet @@ -32,22 +32,24 @@ PartitionsAndPermutations: Exports == Implementation where ST1 ==> StreamFunctions1 ST2 ==> StreamFunctions2 ST3 ==> StreamFunctions3 + macro NNI == NonNegativeInteger + macro PI == PositiveInteger Exports ==> with - partitions: (I,I,I) -> ST L I + partitions: (NNI,NNI,NNI) -> ST L PI ++\spad{partitions(p,l,n)} is the stream of partitions ++ of n whose number of parts is no greater than p ++ and whose largest part is no greater than l. - partitions: I -> ST L I + partitions: NNI -> ST L PI ++\spad{partitions(n)} is the stream of all partitions of n. - partitions: (I,I) -> ST L I + partitions: (NNI,NNI) -> ST L PI ++\spad{partitions(p,l)} is the stream of all ++ partitions whose number of ++ parts and largest part are no greater than p and l. - conjugate: L I -> L I + conjugate: L PI -> L PI ++\spad{conjugate(pt)} is the conjugate of the partition pt. - conjugates: ST L I -> ST L I + conjugates: ST L PI -> ST L PI ++\spad{conjugates(lp)} is the stream of conjugates of a stream ++ of partitions lp. shuffle: (L I,L I) -> ST L I @@ -74,25 +76,26 @@ PartitionsAndPermutations: Exports == Implementation where Implementation ==> add partitions(M,N,n) == - zero? n => concat(empty()$L(I),empty()$(ST L I)) - zero? M or zero? N or n < 0 => empty() - c := map(concat(N,#1),partitions(M - 1,N,n - N)) - concat(c,partitions(M,N - 1,n)) + zero? n => concat(empty()$L(PI),empty()$(ST L PI)) + zero? M or zero? N or n < N => empty() + s := partitions(subtractIfCan(M,1)::NNI,N,subtractIfCan(n,N)::NNI) + c := map(concat(N::PI,#1),s) + concat(c,partitions(M,subtractIfCan(N,1)::NNI,n)) partitions n == partitions(n,n,n) partitions(M,N)== - aaa : L ST L I := [partitions(M,N,i) for i in 0..M*N] - concat(aaa :: ST ST L I)$ST1(L I) + aaa : L ST L PI := [partitions(M,N,i) for i in 0..M*N] + concat(aaa :: ST ST L PI)$ST1(L PI) -- nogreq(n,l) is the number of elements of l that are greater or -- equal to n - nogreq: (I,L I) -> I + nogreq: (I,L PI) -> I nogreq(n,x) == +/[1 for i in x | i >= n] conjugate x == empty? x => empty() - [nogreq(i,x) for i in 1..first x] + [nogreq(i,x)::PI for i in 1..first x] conjugates z == map(conjugate,z) diff --git a/src/algebra/perm.spad.pamphlet b/src/algebra/perm.spad.pamphlet index 51048658..69f33f83 100644 --- a/src/algebra/perm.spad.pamphlet +++ b/src/algebra/perm.spad.pamphlet @@ -343,10 +343,10 @@ removes fixed points from its result. out cyclePartition p == - partition([#c for c in coerceToCycle(p, false)])$Partition + partition([#c::PI for c in coerceToCycle(p, false)])$Partition order p == - ord: I := lcm removeDuplicates convert cyclePartition p + ord: I := lcm removeDuplicates(cyclePartition(p)::L(PI) pretend L I) ord::NNI sign(p) == @@ -483,8 +483,8 @@ Up to [[patch--50]] we did not check for duplicates. fixedPoints ( p ) == complement movedPoints p cyclePartition p == - pt := partition([#c for c in coerceToCycle(p, false)])$Partition - pt +$PT conjugate(partition([#fixedPoints(p)])$PT)$PT + pt := partition([#c::PI for c in coerceToCycle(p, false)])$Partition + pt +$PT conjugate(partition([#fixedPoints(p)::PI])$PT)$PT @ \section{License} diff --git a/src/algebra/permgrps.spad.pamphlet b/src/algebra/permgrps.spad.pamphlet index af907d4e..5d69a574 100644 --- a/src/algebra/permgrps.spad.pamphlet +++ b/src/algebra/permgrps.spad.pamphlet @@ -989,7 +989,7 @@ PermutationGroupExamples():public == private where gens youngGroup(lambda : Partition):PERMGRP I == - youngGroup(convert(lambda)$Partition) + youngGroup(lambda::L(PI) pretend L I) rubiksGroup():PERMGRP I == -- each generator represents a 90 degree turn of the appropriate diff --git a/src/algebra/prtition.spad.pamphlet b/src/algebra/prtition.spad.pamphlet index 1ebd739c..062b1753 100644 --- a/src/algebra/prtition.spad.pamphlet +++ b/src/algebra/prtition.spad.pamphlet @@ -32,20 +32,19 @@ import List Partition(): Exports == Implementation where macro L == List macro I == Integer - macro P == PositiveInteger + macro PI == PositiveInteger macro OUT == OutputForm macro NNI == NonNegativeInteger macro UN == Union(%,"failed") - Exports == Join(OrderedCancellationAbelianMonoid, - ConvertibleTo List Integer,CoercibleTo List Integer) with - partition: L I -> % + Exports == Join(OrderedCancellationAbelianMonoid, CoercibleTo L PI) with + partition: L PI -> % ++ partition(li) converts a list of integers li to a partition - powers: % -> List Pair(I,PositiveInteger) + powers: % -> List Pair(PI,PI) ++ powers(x) returns a list of pairs. The second component of ++ each pair is the multiplicity with which the first component ++ occurs in li. - pdct: % -> I + pdct: % -> PI ++ \spad{pdct(a1**n1 a2**n2 ...)} returns ++ \spad{n1! * a1**n1 * n2! * a2**n2 * ...}. ++ This function is used in the package \spadtype{CycleIndicators}. @@ -53,11 +52,10 @@ Partition(): Exports == Implementation where ++ conjugate(p) returns the conjugate partition of a partition p Implementation == add - Rep == List Integer + Rep == L PI 0 == per nil - coerce(s: %): List Integer == rep s - convert x == copy rep x + coerce(s: %): L PI == rep s partition list == per sort(#2 < #1,list) zero? x == empty? rep x x < y == rep x < rep y @@ -68,7 +66,7 @@ Partition(): Exports == Implementation where zero? n => 0 x + (subtractIfCan(n,1) :: NNI) * x - remv(i: I,x: %): UN == + remv(i: PI,x: %): UN == member?(i,rep x) => per remove(i, rep x)$Rep "failed" @@ -82,14 +80,14 @@ Partition(): Exports == Implementation where powers x == l := rep x - r: List Pair(I,P) := nil + r: List Pair(PI,PI) := nil while not empty? l repeat i := first l -- Now, count how many times the item `i' appears in `l'. -- Since parts of partitions are stored in decreasing -- order, we only need to scan the rest of the list until -- we hit a different number. - n: P := 1 + n: PI := 1 while not empty?(l := rest l) and i = first l repeat n := n + 1 r := cons(pair(i,n), r) @@ -101,7 +99,7 @@ Partition(): Exports == Implementation where i2 = 1 => (i1 :: OUT) ** (" " :: OUT) (i1 :: OUT) ** (i2 :: OUT) - mkexp1(lli: L Pair(I,PositiveInteger)): L OUT == + mkexp1(lli: L Pair(PI,PI)): L OUT == empty? lli => nil li := first lli empty?(rest lli) and second(li) = 1 => @@ -114,7 +112,7 @@ Partition(): Exports == Implementation where pdct x == */[factorial(second a) * (first(a) ** second(a)) - for a in powers x] + for a in powers x] :: PI @ \section{domain SYMPOLY SymmetricPolynomial} diff --git a/src/algebra/sgcf.spad.pamphlet b/src/algebra/sgcf.spad.pamphlet index 5f1dfa6b..72669658 100644 --- a/src/algebra/sgcf.spad.pamphlet +++ b/src/algebra/sgcf.spad.pamphlet @@ -48,6 +48,7 @@ SymmetricGroupCombinatoricFunctions(): public == private where V ==> Vector B ==> Boolean ICF ==> IntegerCombinatoricFunctions Integer + macro PI == PositiveInteger public ==> with @@ -85,7 +86,7 @@ SymmetricGroupCombinatoricFunctions(): public == private where ++ is given in list form. ++ Notes: the inverse of this map is {\em coleman}. ++ For details, see James/Kerber. - listYoungTableaus : (L I) -> L M I + listYoungTableaus : L PI -> L M I ++ listYoungTableaus(lambda) where {\em lambda} is a proper partition ++ generates the list of all standard tableaus of shape {\em lambda} ++ by means of lattice permutations. The numbers of the lattice @@ -95,7 +96,7 @@ SymmetricGroupCombinatoricFunctions(): public == private where ++ Notes: the functions {\em nextLatticePermutation} and ++ {\em makeYoungTableau} are used. ++ The entries are from {\em 0,...,n-1}. - makeYoungTableau : (L I,L I) -> M I + makeYoungTableau : (L PI,L I) -> M I ++ makeYoungTableau(lambda,gitter) computes for a given lattice ++ permutation {\em gitter} and for an improper partition {\em lambda} ++ the corresponding standard tableau of shape {\em lambda}. @@ -107,7 +108,7 @@ SymmetricGroupCombinatoricFunctions(): public == private where ++ to the lexicographical order from bottom-to-top. ++ The first Coleman matrix is achieved by {\em C=new(1,1,0)}. ++ Also, {\em new(1,1,0)} indicates that C is the last Coleman matrix. - nextLatticePermutation : (L I, L I, B) -> L I + nextLatticePermutation : (L PI, L I, B) -> L I ++ nextLatticePermutation(lambda,lattP,constructNotFirst) generates ++ the lattice permutation according to the proper partition ++ {\em lambda} succeeding the lattice permutation {\em lattP} in @@ -280,9 +281,9 @@ SymmetricGroupCombinatoricFunctions(): public == private where nextLatticePermutation(lambda, lattP, constructNotFirst) == - lprime : L I := conjugate(lambda)$PartitionsAndPermutations - columns : NNI := (first(lambda)$(L I))::NNI - rows : NNI := (first(lprime)$(L I))::NNI + lprime := conjugate(lambda)$PartitionsAndPermutations + columns := first(lambda)$L(PI) + rows := first(lprime)$L(PI) n : NNI :=(+/lambda)::NNI not constructNotFirst => -- first lattice permutation @@ -332,9 +333,9 @@ SymmetricGroupCombinatoricFunctions(): public == private where makeYoungTableau(lambda,gitter) == - lprime : L I := conjugate(lambda)$PartitionsAndPermutations - columns : NNI := (first(lambda)$(L I))::NNI - rows : NNI := (first(lprime)$(L I))::NNI + lprime := conjugate(lambda)$PartitionsAndPermutations + columns := first(lambda)$L(PI) + rows := first(lprime)$L(PI) ytab : M I := new(rows,columns,0) help : V I := new(columns,1) i : I := -1 -- this makes the entries ranging from 0,..,n-1 |