--6c2NcOVqGQ03X4Wi
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Dear GAP-Forum,

I sent a message a two months ago about a library I am developing for
computing in invariant rings of permutation groups. In the long term,
I am now pretty much convinced I need to rewrite it using GAP. I would
need advises concerning the first steps. My needs and current state of
development is detailed below.

Thanks in advance for any suggestions and comments,

Nicolas

---------------------------------------------------------------------------=
---
The main basic block I need for this is a set of blindingly fast
routines for isomorphisms problems of lists of integers under
permutation groups. I wrote a standalone C++ library (GLIP,
http://glip.sourceforge.net) to do this. I would like to either
integrate it into GAP, or happily throw it away if GAP already
provides the facilities I need.

Let me be more precise. Let G be a subgroup of the symmetric group Sn
over n elements. G acts naturally on lists of length n by permutation
of the elements (basic action Permuted). I consider here compositions,
i.e., lists of small non-negative integers. To give an order of
magnitude, here is a typical example I would be interested in:

G6:=3DAction(SymmetricGroup(6), Combinations([1..6],2), OnSets)

So, Size(G)=3D720, n=3D15, and by small integers, I mean in the range [0..3=
0].

Here are the different operations I need:
1 Orbit(l), compute the orbit of l
2 Canonic(l) compute the canonical representant of the orbit of l.
(by canonical, I mean for example maximum for lexicographic comparison)
3 IsCanonic(l) test if l is canonical in its orbit
4 CanonicCompositions(d) compute the canonical representants of all
orbits of compositions of sum d
5 CanonicCompositions(l) compute the canonical representants of all
orbits of compositions having the same content as l.

With the example above, 5 amounts to generating multigraphs up to
an isomorphism, and 6, with l=3D[1,1,1,0,...,0], amounts to generating simp=
le
graphs with 3 edges up to an isomorphism. There already exists software
doing this kind of thing (e.g. Nauty by Brendan Mc Kay), but I would
like my library to work more generally with any permutation group.

I would describe my current implementation as not-completely-stupid
brute force. I.e. the full group is directly generated, and a
canonical test which succeeds requires to iterate through the whole
group. On the other hand, the ordering of the elements of the group is
dynamically adapted, so as to statistically quickly reject
compositions that are not canonical. Also, 4 and 5 use orderly
generation techniques, which require almost constant memory space, and
should be reasonably fast, with an average complexity around (size of
the group) x (number of representants).

Using a backtrack algorithm based on stabilizer chains would probably
make canonical tests much faster in the average. It would also avoid
the generation of the group, though it may be worth to remember the
full backtrack tree in between calls to IsCanonic.

---------------------------------------------------------------------------=
---
Here are some technical questions for which I did not manage to find
answers in the manual.

1) To compute the Hilbert series of the invariant ring, and to do
Polya enumeration, I need to know how many permutations of G there
are of each given cycle type. To avoid generating the group, one
way can be to try to find the sizes of the conjugacy class of G,
and the cycle type of their respective elements. Is it possible to
get this information without actually computing
ConjugacyClasses(G)? For example, if G is obtained as the image of
a smaller group G' by some homomorphism, it would be nice to get
the information from G' and the homomorphism instead.

2) I often need to run through the (big) results of Partitions(...),
Combinations(...) or such. Are there non-trivial Iterators for
those structures ?

Related to this, is it possible to define the following action,
without actually generating of all the combinations?

G20:=3DAction(SymmetricGroup(20), Combinations([1..20],2), OnSets)

3) I will have to store a lot of compositions. Since the numbers
involved are small, it seems to be reasonable to store those
compositions as row vectors with coefficient in some small field
(e.g. GF(2^5)). Is the natural action Permuted defined (and
efficient) for such row vectors?

4) Is it possible to construct an infinite dimensional algebra by
providing an infinite set of linearly independent generators and
specifying the multiplication table through a function:
F(gen,gen) -> linear combination of generators ?

5) Is the "division by increasing powers" of univariate polynomials
implemented ?

6) I know a few persons would who have about the same needs as me for
the isomorphisms problem I stated above. However, they specifically
need a library that can be linked into another software. If the
final implementation is in GAP, is it technically possible to make
a (static or dynamic) module containing just the strictly necessary
parts of GAP ?

--=20
Nicolas M. Thi=E9ry "Isil", 412 Washington Avenue, 80403 Golden Colorado (U=
SA)
M=E9l: nthiery@mines.edu, T=E9l: (303)273-5492, Fax: (303)273-3875
WWW: <URL:http://www.mines.edu/~nthiery/>

--6c2NcOVqGQ03X4Wi
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.0 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE5wwVm6iQOIqkrTMQRAjzqAJ0U9R9dN1WJCLHizXKA28fGrRCFOQCfRV5M
bh+/aTNwHt43IqTPWLEUc3c=
=oHph
-----END PGP SIGNATURE-----

--6c2NcOVqGQ03X4Wi--