Martin Baker wrote:
>
> I find it hard to understand the functions in PermutationGroup. Partly
> because I cant find any documentation (I searched the usual places but
> its easy to miss things) and its hard to follow the code because Rep is
> so complicated.
Algorithm is described in A. Seress book "Permutation group algorithms",
but I do not think this book is freely available. On the net
there are notes by A. Hulpke which contain sketch of the algorithm.
Data structure in a sense are very natural once you know what
algorithms are supposed to do. More precisely, we have:
Rep := Record(gens : L PERM S, information : REC2)
REC2 ==> Record(order : NNI, sgset : L V NNI, _
gpbase : L NNI, orbs : V REC, mp : L S, wd : L L NNI)
REC ==> Record ( orb : L NNI, svc : V I )
in REP gens are original generators, information is extra
data coded in efficient form. In particular, instead of
S internal computation works with integers: we first create
list of points appearing in all permutation and for internal
purposes we replace elements by position in the list.
Permutations are represented by vectors of integers, so
that v(i) gives image of point i. Now in REC2 order is
number of elements in the group. Value zero has special
meaning -- it means that no information is computed.
sgset is strong generators, gpbase is list of base points,
mp is list of elements of S moved by some permutation
(needed for mapping between permutations on S and
internal representation), wd gives representation of
strong generators in terms of orignal generators.
The most interesting structure is orbs which describes
orbits of base point. The orb part is just list of
point on the orbit. The svc part allows you to
compute element of the group moving given point to
base point of the orbit. In detail, -2 means point
not in orbit, -1 means base point, positive value
is index of strong generator moving given point
closer to base point (look at 'strip' to see how
this is used).
Given that I know how presentation of permutation
group can be dane and that I know structure of
PermutationGroup I decide to code the convertion.
I need to do more test, but at least S5 seem to
work correctly.
I also noticed that Todd-Coxeter (toPermutationIfCan)
may produce something strange. Namely, the following
(junky) relations:
[[4,4,- 3,- 2,- 1,- 4,- 3], [3,4,- 2,- 4,- 3,- 2], [2,4,- 4,- 3,- 2],
[1,4,- 4,- 3,- 1], [4,4,- 3,- 2,- 1,- 4,- 3,- 1], [3,4,- 2,- 4,- 3,- 1],
[2,4,- 1,- 4,- 3], [1,4,- 4,- 3], [4,4,- 3,- 2,- 1,- 4,- 3,- 2],
[3,4,- 1,- 2,- 1,- 4], [2,4,- 1,- 4,- 3,- 1], [1,4,- 1,- 4,- 3,- 2], [4,4],
[3,4,- 4,- 3], [2,4,- 2,- 4], [1,4,- 1,- 4], [3,3,- 2,- 3,- 2],
[2,3,- 3,- 2], [1,3,- 3,- 1], [3,3,- 2,- 3,- 1], [2,3,- 1,- 3], [1,3,- 3],
[3,3,- 1,- 2,- 1], [2,3,- 1,- 3,- 1], [1,3,- 1,- 3,- 2], [2,2,- 1],
[1,2,- 2], [2,2,- 1,- 2,- 1], [1,2,- 2,- 1], [1,1]]
and [1, 2, 3, 4] as generators produced set of permutations
on 6 elements which generates full symmetric group. The
presentation above is junky because relation [1,2,- 2]
means that 1 is identity. Then relation [2,2,- 1,- 2,- 1]
simplifies to [2,2,- 2] and next [2] which means that 2
is identity. Then [3,3,- 2,- 3,- 1] means that 3 is
identity and [4,4,- 3,- 2,- 1,- 4,- 3] means 4 is
identity, so we get trivial group.
BTW: can you get smaller number of point than number of
elements in the group? All correct examples I saw
produce just permutation representation on itself.
However, Todd-Coxeter in general produces representation
on cosets of a subgroup, so if you take notrivial
subgroup the set on which permutation act will be
smaller than the whole group.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
