The Mathematica Package PERMS
B. Fiedler
Eichelbaumstr. 13, D04249 Leipzig
email: bfiedler@fiemath.de
March, 1999
1 General characteristics of PERMS
The program package PERMS,
version 2.1 (15.1.1999)^{1}
is a Mathematicapackage. It
is a collection of tools for investigations of permutation groups and for
doing calculations in the representation theory of symmetric groups. These
tools can be used together with the full power of the Mathematicasystem.
PERMS
runs under Mathematica 2.x [2] and 3.x
[3]. It works without Mathematica frontends.
Thus it can used without difficulties under all operating systems and on all
machines for which Mathematica is available.
The present version makes available 187 tools which are collected in a
context Perms`. In the next section we present a selection of 137
of these tools. All tools in Perms` are fitted out with help texts
which can used by means of the help system of Mathematica. These texts are stored in
the file usage.m (80197 Byte). Of course, a user can also work
with
all (internal) tools which are not contained in the context Perms`
since all sources are accessible.
The following statistics characterize the files of
PERMS:
files  number  name  byte 
source code  29   354279 
data  3   
  ftdata.m  331766 
  chartab.m (small)  40221 
  chartab.m (full)  2324983 
The file ftdata.m contains the precomputed data for the discrete
Fourier transform. Character tables are stored in the files chartab.m.
The user can choose between a small version of chartab.m which
contains the character tables of S_{2} , ¼, S_{10} and a long
version of chartab.m comprises the character tables of
S_{2} , ¼, S_{17}. We have observed the following costs for the
load process of PERMS
under the conditions (1) in Section
..
  memory 
 time  for loading  after loading 
with small chartab.m  33.66 s  1921708 byte  1721012 byte

with full chartab.m  236.44 s  13549484 byte  7915796 byte 
The long version of chartab.m has only to be loaded if values of
characters of symmetric groups S_{r} with r > 10 are needed.
We do not store the original files chartab.m on the hard disk but
compressed files which will be uncompressed during the load process. Under
MSDos
we use pkzip/pkunzip to this end. Only the use of such a compression
utility has to be modified if a transfer of PERMS
to an other operating
system is intended.
We have made many efforts to get a high working speed of PERMS.
Since Mathematica uses an extensive set of rules to evaluate a given expression,
it can happen that Mathematica makes unnecessary attempts to change an expression
by means of rules which can be neglected or have no effect in the given
situation.
The reduction of the number of such superfluous attempts of evaluation is an
important factor to increase the speed of a program.
To achieve such a reduction,
we have found out by the Mathematicatool TraceDialog
which
single steps every PERMStool carries
out during a run. Then we have modified the implementations of the
PERMStools to eliminate unnecessary evaluation steps.
We have kept to a great extent the principle to omit any tests of the
correctness of the input for the PERMStools.
Thus a user has to make sure
himself whether the input fulfils all conditions required by a tool.
However, this principle also involves the advantage that the use of a
PERMStool
in a program package which calls very often this tool have more
favourable costs in calculation time.
PERMS
uses own data types or types of expressions identified by the
following heads:
head  expression 
GLoop  loop in a Cayley graph 
GWord  word defined by a path of a Cayley graph 
HoldList  list of elements 
Parti  partition of a natural number 
Perm  permutation 
Tableau  Young frame or Young tableau 
TabRow  row of a Young tableau 
Type  type of a natural number 
To all these heads the attribute HoldAll is assigned. This attribute
causes that no subexpression of an expression with one of the above heads is
automatically evaluated by Mathematica. An evaluation of such subexpressions is
carried out only then if it is required by an instruction of
PERMS. This
helps to avoid unnecessary evaluations.
The use of the above own data types had a further favourable effect.
PERMS turned out to be
insensitive to modifications in Mathematica 3.x which are not compatible with the
standard of Mathematica 2.x (see [3]).
Mathematica can evaluate
these data types only by means of rules from PERMS.
We have not discovered
up to now a rule of PERMS
which does not work correct under Mathematica 3.x.
Our program does not use any Mathematicatool from the list in
[3].
An investigation (by means of TraceDialog) whether unnecessary
evaluations again arise under Mathematica 3.x has not yet
been carried out for all tools of PERMS.
2 A list of tools of PERMS
(i) Tools for the investigation of permutation groups
 GeneratedGroup
 determines all elements of the group
G = áP ñ generated by a given set P Í S_{r} of
permutations.
 SymmetricGroup
 determines the set of all elements of a
symmetric group
S_{r} of a given natural number r Î N.
 Subgroup:
 Let G be a permutation group and P be a property
characterizing a subgroup H = { g Î G  P(g) = true }.
Subgroup determines the set H and a set of generators of
H.
 Centralizer
 determines the centralizer
C (S)
of a subset
S Í G within a given permutation group G.
 Normalizer
 determines the normalizer
N (S)
of a subset
S Í G within a given permutation group G.
Cayley graph and defining relations of a permutation group
[1]
 CayleyGraph
 generates the Cayley graph
G (G,S)
of a small permutation group G
with a given set S of generators.
 PermPos
 determines the position of a permutation p within a
given
set S Í S_{r} of permutations.
 Perm2Node
 determines the node in G(G,S) which represents
a given permutation p Î G.
 Node2Perm
 determines the permutation p Î G which is
represented
by a given node of a Cayley graph G (G,S) of G.
 EdgeValue:
 If an edge (p_{1} , p_{2}) of a Cayley graph
G (G,S) is
given, then the tool
EdgeValue yields that generator s Î S which satisfies
p_{2} = s °p_{1}.
 SpanningTree
 determines a spanning tree T of a given Cayley
graph
G (G,S).
 BackTraceST
 determines the sequence of nodes which leads from
the root
id to a given node p within a given spanning tree T of a Cayley
graph G (G,S).
 DepthST
 yields the number of nodes within a longest path in a
given
spanning tree T from the root id to a leaf of T.
 TreeWord
 yields the sequence of generators (word) which is
given by the values of
EdgeValue on the edges of a path from id to a given node
p within a given spanning tree T.
 LoopCG:
 Let T be a given spanning tree and (p_{1} , p_{2}) be
an
edge of a given Cayley graph G (G,S). Then LoopCG yields the word
w_{2}^{1} °s °w_{1} where
w_{i} : = TreeWord[p_{i},T]
and s : = EdgeValue[p_{1} , p_{2}].
 SetOfDefiningRelations
 determines a set of defining relations
for given generators
S of a permutation group G from a Cayley grapg G (G,S) and a spanning
tree T of G (G,S) by colouring the Cayley graph (see
[1]).
Cyclic extension method (see [1])
 ZGenerators:
 Let G be a permutation group.
ZGenerators determines
a generating element s_{i} for every cyclic subgroup C_{i} Í G of
prime power order p_{i}^{ni} and forms the set Z of all these s_{i}.
 TestElements
 calculates the element s_{i}^{pi} for every
s_{i} Î Z.
The tool NextLayer needs the
s_{i}^{pi} as test elements.
 FirstLayer
 determines layer 1 of the subgroup lattice of G.
Layer 1
consists of all cyclic subgroups of G with prime order.
 FirstGroups:
 Let k be a given layer number.
FirstGroups
determines all cyclic subgroups
ás_{i} ñ, s_{i} Î Z, which lie in the kth layer. (Such a
group has an order p_{i}^{ni} with n_{i} = k.)
 NextLayer:
 If a permutation group G, the set Z and the
(k1)th layer of the set of solvable subgroups of G are given, then
NextLayer determines the kth layer of solvalble subgroups of G.
 LayerEmbedding:
 Toll which is useful in the search of all
subgroups of a
full S_{r}. Assume that all layers of the subgroup
lattice of S_{r1} are given. LayerEmbedding applies
ClassesOfEmbeddedGroups to the kth layer of S_{r1} and
generates a subset of the kth layer of S_{r} in this way.
 CommutatorgroupLattice
 calculates the commutator group G¢ of
a given permutation
group G and afterwards the lattice of all subgroups H with
G¢ Í H Í G.
 OneOrbit:

Let S be a given set of generators of a group
G Í S_{r} and l Î {1 , ¼, r} be a given natural number.
OneOrbit calculate the orbit
l^{G} : = { p(l)  p Î G } of l and a Schreier vector
and a backward
pointer list of l^{G} relative to S.
 AllOrbits:
 Let S be a given set of generators of a group
G Í S_{r}. AllOrbits determines all orbits of G, a
Schreier vector and a backward pointer list relative to S.
 SchreierTrace:
 Let v be a given Schreier vector found by
AllOrbits and
l Î {1,¼,r} be a given point. SchreierTrace determines a
permutation p Î G which fulfils l = p(l_{0}) where l_{0} Î l^{G} is the
representative of l^{G} defined by v.
 CyclicGroup
 determines the cyclic group áp ñ
which is
generated by a given permutation p.
 CommutatorGroup
 calculates the commutator group G¢ of a given
permutation
group G.
 Stabilizer
 yields the stabilizer
G_{I} : = { p Î G  " i Î I: p(i) = i }
of a given permutation group G Í S_{r} and a given point set
I Í { 1 , ¼, r }.
 ConjClass
 calculates the conjugacy class of a given permutation
p within a permutation group G which is defined by a given set S of
generators.
 AllConjClasses
 determines all conjugacy classes of a given
permutation group G with a given set S of generators of G.
 SnConjClasses
 determines all conjugacy classes of a given
symmetric group S_{r}.
 CardConjClass
 calculates the cardinality of a conjucacy class
of a S_{r} which is characterized by a type or a partition of r.
 ConjClassPosNumbers
 transforms every conjugacy class
C Ì S_{r} into a a set
{ PermNumber[p]  p Î C } of position numbers
(see description of PermNumber in (ii)).
 AllConjugateGroups
 determines all conjugate subgroups of a
given subgroup H of a given permutation group G.
 ClassesOfConjGroups:
 Let { H_{1} , H_{2} , ¼} be a given
list of subgroups of a given permutation group G. The tool determines all
such classes of conjugate subgroups of G which contains at least one of the
groups H_{i}.
 ClassesOfEmbeddedGroups:
 Let { H_{1} , H_{2} , ¼} be a
set of subgroups of a S_{r1}. The tool produces the natural embeddings
H_{i} ® H¢_{i} Í S_{r} of all H_{i} into S_{r} and
applies ClassesOfConjGroups to the set
{ H¢_{1} , H¢_{2} , ¼}. (See Embedding.)
 ClasslistToGrouplist
 transforms a list of classes of conjugate
groups into a simple list of the groups of these classes (a use of the
Mathematicatool Flatten).
 Embedding
 maps permutations p Î S_{m} onto permutations
q Î S_{n}, m < n, according to the rule
where D is an integer with 0 £ D £ n  m which can be
chosen by the user. If expr is an expression which contains
permutations p Î S_{n}, then Embedding replaces all these
permutations by their images in S_{n}. The tool Embedding is used in
ClassesOfEmbeddedGroups with D = 0.
 DirectProduct:
 If G_{1} , G_{2} Í S_{r} are subgroups
which fulfil the conditions of an internal direct product, then
DirectProduct generates the set of the elements of
G_{1} ×G_{2}.
 LeftCosets
 If a permutation group G and a subgroup
H Í G are given, then LeftCosets generates all left cosets
of G relative to H.
 LeftCosetReps
 determines a set of representatives of the left
cosets of a given permutation group G relative to a given subgroup
H Í G.
 RightCosets
 If a permutation group G and a subgroup
H Í G are given, then RightCosets generates all right cosets
of G relative to H.
 RightCosetReps
 determines a set of representatives of the right
cosets of a given permutation group G relative to a given subgroup
H Í G.
 Ord[p]
 calculates the order of a given permutation
p.
 MaxOrder
 determines
max{ Ord[p]  p Î S_{r} } for a given symmetric
group S_{r}.
 FirstAppearance
 yields the smallest number r Î N
for which
a given number k Î N occurs as order of an element p of the
symmetric group S_{r}.
 AllOrders
 gives a list of all orders which occur among the
elements of a given symmetric group S_{r}.
 ModuloOrder:
 If N Í G is a normal subgroup of a
permutation group G and p Î G is an element from G, then
ModuloOrder yields the order of the element p °N of the factor
group G/N.
 OrderSets
 arranges the elements of a given permutation group
G in subsets whose elements have the same order.
 MaxOrderElements
 yields the list of the elements with maximal
order from a given permutation group G.
 SmallGroupGenerators
 determines a set of generators S for a
given small permutation group G in the following way: If a subset S¢ of
generators of G is already found, then the first element of the list
G\áS¢ñ is choosen as further generator of G
and added to S¢.
 SmallGroupOrdGenerators
 is a modification of
SmallGroupGenerators: The tool chooses an element of maximal order
from G\áS¢ñ as further generator of G.
(ii) Group ring tools
 PermProd
 calculates the product a_{1} ·a_{2} of two given
group ring elements a_{1} , a_{2} Î C [S_{r}].
Especially, PermProd is used to determine the
product p_{1} °p_{2} of two permutations p_{1} , p_{2} Î S_{r} in
PERMS.
 PermPower
 calculates powers p^{k}, k Î N, of a given
permutation p.
 InvPerm
 calculates the inverse element p^{1} of a given
permutation p.
 IdPerm
 yields the identity element id Î S_{r} of a given
symmetric group S_{r}.
 Commutator
 calculates the commutator
p °q °p^{1} °q^{1} of two given permutations
p , q Î S_{r}.
 PermNumber
 determines the position (described by a natural
number) of a
given permutation p within the lexicographically ordered list of
the elements of the symmetric group S_{r} which contains p.
 Star[a]
 calculates the element
a^{*} = å_{p Î Sr} a(p) p^{1}
from a given group ring element
a = å_{p Î Sr} a(p) p Î C [S_{r}].
 NumVal
 replaces all coefficients of a given group ring
element a Î C [S_{r}] by numerical approximate values of these
coefficients.
The user can choose the digit
precision to which the tool calculates the aproximate
values.
 FirstPermutation
 searches a given expression expr for
permutations. If a permutation p is found within expr, then the
search is stopped and p is returned.
 FactorOfPerm
 returns the coefficient a(p)
which stand by a given
permutation p within a given group ring element
a = å_{p Î Sr} a(p) p Î C [S_{r}].
 AllFactors
 returns the list of all coefficients a(p) of a
given group ring element
a = å_{p Î Sr} a(p) p Î C [S_{r}].
 ToMapping:
 If
a = å_{p Î Sr} a(p) p Î C [S_{r}] is a given group ring
element, then ToMapping produces a list^{2}
A = { a_{1} , a_{2} , ¼, a_{r!} } where
a_{i} = a(p) if i = PermNumber[p]. This list A describes
a mapping i ® a_{i}.
 Split:
 If a group ring element
a = å_{p Î Sr} a(p) p Î C [S_{r}] is given, then
Split produces the list of all permutations p within a and the
list of all coefficients a(p) of a. The arrangements of the elements of
these lists correspond to each other.
 PermCollect
 Let a Î C [S_{r}] be a given group ring
element. PermCollect collects together terms of a that involve the
same permutation p.
 Support
 yields the support { p Î S_{r}  a(p) ¹ 0 } of a given group ring element
a Î C [S_{r}].
The result is an unsorted list of permutations which
several times contains such
permutations that repeatedly occur in a.
 OrdSupport
 yields the support of a given group ring element
a. The result is an ordered list of permutations which contains
no multiple elements.
 Projection
 determines the projection
proj_{M} a = å_{p Î M} a(p) p of a given group ring element
a = å_{p Î Sr} a(p) p onto a given set M Í S_{r} of
permutations.
 IsotropyGroup
 determines the isotropy group
C_{a} : = { p Î S_{r}  $ m(p) Î C : p·a = m(p) a } of a given group ring element
a Î C [S_{r}].
 IsoHom:
 Let a Î C [S_{r}] be a group ring element and
p Î C_{a} be an element of the isotropy group of a. Then IsoHom
yields that complex number m(p) Î C which fulfils
p ·a = m(p) a.
 KerIsoHom
 determines the kernel
kerm = { p Î C_{a}  m(p) = 1 } of the above Homomorphism
m: C_{a} ® C belonging to the isotropy group of a given
group ring element a Î C [S_{r}].
 Char1Dat4IsoHom:
 The above homomorphism
m: C_{a} ® C is a 1dimensinal character of C_{a}. The tool
calculates the data {ker,reps,mus} from m
where ker is the kernel of m, reps is a set of
representatives of the cosets of C_{a} relative to ker and mus
is a list of the values of m on the elements of reps. A structur
{ker,reps,mus}
is expected by PERMS for data of a 1dimensional
character.
(iii) Partitions, types, tableaux
 AllPartitions
 generates all partitions l  r
of a given natural number r Î N.
 LongPartition
 transforms the short form of a given partition
l  r into the long form of l.
 ShortPartition
 transforms the long form of a given partition
l  r into the short form of l.
 MakePartition
 determines the partition l  r which
belongs to a given Young tableau or Young frame.
 Part2Type
 transforms a given partition l  r of a
natural number r into a type r  r of r.
 Type2Part
 transforms a given type r  r of a
natural number r into a partition l  r of r.
 AllTypes
 determines all types r  r of a given
natural number r Î N.
 Perm2Part
 calculates the cycle partition of a given permutation
p.
 PartMult
 calculates the partition
k l = (k l_{1} , k l_{2} , ¼), k Î N,
from a given
partition l = (l_{1} , l_{2} , ¼).
 AllDecompositions
 determines all decompositions
q  = r of a given natural number r Î N.
 MakeFrame
 generates the Young frame [l] of a given
partition l  r. All boxes of [l] are filled with 0.
 StandardTableaux
 determines the set ST_{l} of all
standard tableaux of a given partition l  r.
 FilledFrame
 generates the lexicographically smallest standard
tableau t Î ST_{l} of a given partition l  r.
 TransposeTableau
 produces the transposed tableau of a given
Young tableau.
 DefTableau
 tool which allows a convenient input of a Young
tableau by hand.
 YoungFactor
 determines from a given partition
l  r that factor c Î Q which transforms every Young
symmetrizer y_{t}, t Î T_{l}, of l into an idempotent
c y_{t}.
 PartDim
 determines the dimension dimC [S_{r}]·y_{t} of every left ideal
C [S_{r}]·y_{t} generated by a Young symmetrizer
y_{t}, t Î T_{l}, of a given partition l  r by
means of the hook length formula from l.
 FrameDim
 produces the same result as PartDim
using a Young frame [l] or a Young tableau t Î T_{l} as
input.
 CombLemmaQ:
 Let t_{1} , t_{2} Î T_{l} be two given
Young tableaux of a partition l  r. CombLemmaQ
yields True if no column of t_{1} contains two numbers which lie in
t_{2} in the same row. Otherwise, CombLemmaQ yields False.
(Compare with the Combinatorial Lemma ..)
 PTCompose
 calculates the composition p °t of a given
permutation p Î S_{r} and a given Young tableau t Î T_{l},
l  r.
 TransPerm:
 Let t_{1} , t_{2} Î T_{l} be two given Young
tableaux of a partition l  r. TransPerm determines that
permutation p Î S_{r} which fulfils t_{1} = p °t_{2}.
 DecomposedTransPerm
 yields
s = TransPerm[t_{1} , t_{2}] and the decomposition
s = p °q of s with p Î H_{t2}, q Î V_{t2}.
 AllTransPerms:
 Let { t_{1} , t_{2} , ¼} be a given list
of Young tableaux t_{i} Î T_{l} of a partition l  r.
AllTransPerms calculates the list { s_{1} , s_{2} , ¼} of that
permutations s_{i} Î S_{r} which fulfil t_{i} = s_{i} °t_{1} for all i.
(iv) Special idempotents and generating elements
 HorizontalPerms
 generates the group H_{t} of all horizontal
permutations of a given Young tableau t.
 VerticalPerms
 generates the group V_{t} of all vertical
permutations of a given Young tableau t.
 HorizontalSum
 calculates the sum
å_{p Î Ht} p of all horizontal permutations of a given Young
tableau t.
 VerticalSum
 calculates the alternating sum
å_{q Î Vt} c(q) q
of all vertical permutations of a given
Young tableau t. Here c(q) denotes the signature of q.
 YoungSymmetrizer
 determines the Young symmetrizer y_{t} of a
given Young tableau t.
 CentralGenerator
 determines the symmetrizer c_{l} of
an irreducible character c_{l} of a symmetric group S_{r} (see
Proposition .). The
tool needs as input the list of all conjugacy classes of S_{r} and the
partition l  r that characterizes the character
c_{l}.
 Char1Idempotent:
 Let c be a 1dimensional character of a
permutation group G Í S_{r}. The tool yields the idempotent which
is proportional to the symmetrizer of c.
Group ring elements^{3}
connected with Solomon's algebra (see Section .)
 LieXi[q]
 calculates the element X^{q} of a given
decomposition q  = r of a natural number r Î N.
 LieOmegaProd
 generates the element w^{q} of a given
decomposition q  = r.
 LieOmega
 calculates the element
w_{q} = X^{q} ·w^{q} for a given decomposition
q  = r.
 NuFactor
 calculates the number [1/ q?] from a given
decomposition q  = r. The multiplication with [1/ q?]
transforms
w_{q} into an idempotent n_{q} = [1/ q?] w_{q}.
 LieNu[r]
 calculates the idempotent
n_{r} = ^{1}/_{r} w_{r} of a given natural number r Î N.
 Char1LieZeta:
 Let r Î N be a given natural number. The
tool calculates the data of the 1dimensional character
f: (1 2 ¼r )^{k} ® r^{k},
r: = exp([(2pi)/ r]), of the cyclic group
C = á(1 2 ¼r ) ñ (see Section
.).
 LieZeta
 calculates the idempotent z_{r} of a given
natural number r Î N (see Section
.).
 TestIdempotent:
 Let y Î C [S_{r}] be a Young
symmetrizer and a Î C [S_{r}] be a group ring element with
y ·a ¹ 0. The tool determines a generating idempotent of the
minimal left ideal C [S_{r}] ·y ·a searching for a
permutation p Î S_{r} with y ·a ·p ·y ¹ 0 (see
Section .).
Tools, concerning tensor investigations
 GenerateVTuples:
 Let l , n Î N be given natural numbers and
{ i_{1} , ¼, i_{s} } be a finite sequence of narural numbers from
{ 1 , ¼, n }. The tool generates all sequences
{ m_{1} , m_{1} , m_{2} , m_{2} , ¼, m_{l} , m_{l} , i_{1} , ¼, i_{s} },
m_{k} Î { 1 , ¼, n }, which represent tuples
b = (n_{m1} , n_{m1} , ¼, n_{ml} , n_{ml} , n_{i1} , ¼,n_{is} ) Î B_{b0} 

of (basis) vectors from a vector space V where
b_{0} = (n_{i1} , ¼, n_{is} ) is a given subtuple.
 MinimalGrouping:
 Let { i_{1} , ¼, i_{r} } be a sequence of natural numbers that
represents a vector tuple
b = ( n_{i1} , ¼, n_{ir} ) Î B^{r} of basis vectors of a
finitedimensional vector space V. The tool determines that number sequence
{ j_{1} , ¼, j_{r} } which corresponds to the smallest grouping
( n_{j1} , ¼, n_{jr} ) = ál; w_{i} ñ of b.
Furthermore, the tools calculates the grouping partition
l = b^{  } and a permutation p which fulfils
b = p ál; w_{i} ñ.
 GroupingData
 Let B_{b0} be a set of vector tuples represented by finite number
sequences (see GenerateVTuples). The tool determines the sets
L_{b0} and M_{b0 , l} and returns

ì í
î


ì í
î

l, { (ál; w_{i} ñ,a_{ál; wi ñ})  ál; w_{i} ñ Î M_{b0 , l} } 
ü ý
þ


ê ê

l Î L_{b0} 
ü ý
þ



(see Theorem in ).
The minimal groupings ál; w_{i} ñ are represented by
finite number sequences, too. The mapping p required for the
calculation of a_{ál; wi ñ} is given by the procedure
MinimalGrouping.
(v) Characters, LittlewoodRichardson rule, plethysms
 MurNak
 Let l  r be a partition characterizing an
irreducible character c_{l} of a symmetric group S_{r} and
m  r be a partition characterizing a conjugacy class of S_{r}.
MurNak[l, m] calculates the value of
c_{l} on the class of m using the MurnaghanNakayama
formula. If 2 £ r £ $CharTabLimit, then
MurNak reads the values of characters from precomputed character
tables.
 CharTab[r]
 is a variable which contains the character table
of S_{r}.
 TICharTab[r]
 is a variable which contains the transposed
inverse matrix of the matrix of the charactertable of S_{r}.
 PartTab[r]
 contains the list of all partitions
l  r of the natural number r Î N. This list is used to
number the rows and columns of the matices
CharTab[r] and TICharTab[r].
 $CharTabLimit
 is a system variable which contains the
maximum of all natural numbers r ³ 1 for which data
CharTab[r], TICharTab[r] and PartTab[r] exist in
PERMS.
Its present value is $CharTabLimit = 17.
 NextCharTab
 is a tool which allows the user to calculate
the data
CharTab[r+1], TICharTab[r+1] and PartTab[r+1] with
r = $CharTabLimit and to add them to the system of
precomputed data of PERMS.
 Char1Data:
 Let G be a permutation group and N Í G
be a normal subgroup such that the factor group G/N is cyclic. Further let
p Î G be a representative of a generator p °N of G/N. Then
Char1Data[G , N , p] calculates the data
{ker,reps,mus} (see Char1Dat4IsoHom) which describe the
1dimensional character m: G ® C that fulfils
m(p) = exp([(2pi)/ k]), k = G/N, and kerm = N.
 Char1Value
 Let dat = {ker,reps,mus} be the given data of
a 1dimensional character m of a permutation group G and p Î G be
an element of G. Then
Char1Value[p,dat] yields the value m(p).
 Char1Multiplicity
 Let dat = {ker,reps,mus} be the data of a
1dimensional character m of a permutation group G Í S_{r} and
l  r be a partition which characterizes an irreducible
character c_{l} of S_{r}. Then
Char1Multiplicity[l,dat] calculates the multiplicity
ác_{l}_{G} , mñ_{G}.
 AllChar1Multiplicities
 calculates all multiplicities
ác_{l}_{G} , mñ_{G}
for a given 1dimensional character m: G ® C and all
irreducible characters c_{l} of a given symmetric group S_{r}
with G Í S_{r}.
 InvChar1
 replaces the values m_{1} , m_{2} , ¼
in the set mus = { m_{1} , m_{2} , ¼} of the data
{ker,reps,mus} of a 1dimensional character m by
[1/( m_{1})] , [1/( m_{2})] , ¼. Thus the character
[1/( m)] = [`(m)] is obtained.
 RLRule
 calculates the LittlewoodRichardson product
[l_{1}][l_{2}]¼[l_{k}] of a given sequence of
partitions l_{i}  r_{i}. The first argument of the tool is
allowed to be a linear combination
å_{m  r1} c_{m} [m], c_{m} Î N.
 Plethysm
 calculates the plethysm [m]Ä[n] of two
irreducible representations [m] , [n] of symmetric groups
S_{m} , S_{n}, respectively, using the formula of F. Sänger
(see () and () in Chapter ).
 IdPotCM
 Let l = C [S_{r}]·e be a left ideal
generated by a given idempotent e Î C [S_{r}] and C be the set of
conjugacy classes of S_{r}.
The tool calculates
the values c(l) of the character c of the representation
w_{Sr}_{l} and the multiplicities m_{l} of the
decomposition of l into minimal left ideals. For more details see
Section ..
 LongIdPotCM
 is a modification of IdPotCM which works
more efficiently than IdPotCM if e is a long idempotent.
(See Section ..)
(vi) Discrete Fourier transform
 FourierTransform

calculates the natural projection
D_{l}(a) of the discrete Fourier transform D(a) defined by Young's
natural representation of S_{r}
where a Î C [S_{r}] is a given group ring
element and l  r is a given partition characterizing a minimal
twosided ideal a_{l} of C [S_{r}] (see Theorem
.).
 InvFourierTransform
 Let l  r be a partition and
A Î C^{nl×nl} be a matrix with
n_{l} = PartDim[l]. Then
InvFourierTransform calculates (D_{al})^{1}(A)
by means of Fourier Inversion Formula () in Chap.
where
D is the discrete Fourier transform defined by Young's natural
representation of S_{r} and a_{l} is the minimal twosided ideal
of C [S_{r}] characterized by l. If, further, a subset
M Ì S_{r} of permutations is given, then
InvFourierTransform calculates the projection
proj_{M} (D_{al})^{1}(A).
 MakeFourierData
 calculates the data sets
D_{t} for all standard tableaux t Î ST_{l} of a given
partition l  r. These sets D_{t} are used by
PERMS as
precomputed data for the discrete Fourier transform. A user can extend the
present system of such precomputed data by
means of this tool.
 FTData[r]
 contains all precomputed data D_{t}
for the S_{r}
generated by means of MakeFourierData.
 $FourierLimit
 is a system variable that contains the
greatest number r Î N for which precomputed data D_{t} exist and
discrete Fourier transforms can be carried out by
PERMS. Its present value
is $FourierLimit = 8.
 MakeInvFourierData
 calculates the set
data = { D_{l}(p^{1})  p Î M } where
M Í S_{r} is a
given set of permutations and l  r is a given partition.
This set data can be used by DataInvFourierTransform to
determine proj_{M} (D_{al})^{1}(A).
 DataInvFourierTransform
 calculates proj_{M} (D_{al})^{1}(A) for a given matrix A and
a given permutation set M using a data set data which is generatet
by means of MakeInvFourierData from M. The use of the pair
MakeInvFourierData and DataInvFourierTransform works quicker
than InvFourierTransform if proj_{M} (D_{al})^{1}(A)
has to be calculated for many matrices A since
InvFourierTransform repeatedly determines the elements of data
for every matrix A.
References
 [1]

G. Butler.
Fundamental Algorithms for Permutation Groups, volume 559 of
Lecture Notes in Computer Science.
SpringerVerlag, Berlin, Heidelberg, New York, 1991.
 [2]

Stephen Wolfram.
Mathematica.
AddisonWesley, Bonn, München, Paris, Reading, Mass., 2. edition,
1992.
In German.
 [3]

Stephen Wolfram.
Das MathematicaBuch.
AddisonWesleyLongman, Bonn, Reading, Mass., Menlo Park, Cal., New
York, Harlow, Don Mills, Sydney, Mexico City, Madrid, Amsterdam, 3. edition,
1997.
Footnotes:
^{1} Some examples in
this paper were calculated by means of PERMS,
version 2.1 (23.3.1998). The
above newer version of PERMS
is identical with this older version up to
the five
tools GenerateVTuples, MinimalGroupings,
GroupingData, MakeInvFourierData,
DataInvFourierTransform which are added to PERMS
1999. No other
tool
of PERMS
calls these five tools. Thus all calculations which do not use
one of these five tools have the same course under both versions.
^{2} The coefficient list
generated by AllFactors contains only the nonvanishing coefficients
of a.
^{3} Only a part of
the following group ring elements are Lie idempotents or proportional to Lie
idempotents. We have used the substring Lie in all names of these
tools so that a user can easily find them by means of the
help system of Mathematica entering ?Lie*.
File translated from T_{E}X by T_{T}H, version 2.10. On 17 Jul 1999, 01:17.
