Conjugacy classes: Sage vs GAP

[javier]

Hi all,

I have been lately doing some work that required me to explicitly
compute conjugacy classes of certain finite groups.

Since in sage there is no built-in function for that I defined my own
in the obvious straight-forward way:

sage: def conjugacy_class(g,G):
... cc = Set([x*g*x^(-1) for x in G])
... return cc

this feels very pythonic and works just fine, but is terribly
inefficient since it requires a lot of computations and stores in
memory an array of the whole size of the group G before deleting
duplicates. As GAP has a function for computing the conjugacy class of
an element, I decided to wrap it and compare it with the naive
implementation above, coming up with this:

def conjugacy_class_gap(g,G):
... GG = G._gap_()
... gg = g._gap_()
... cc = GG.ConjugacyClass(gg).AsList().sage()
... return Set([G(x) for x in cc])

the coercions in the last line produce a bit of overhead, but are
necessary to be sure that I get a working sage object once I am done.
Even with that extra overhead, the time difference between the two
functions is quite noticeable, GAP being about 20x faster than naive
for small groups:

sage: %time
sage: G = SymmetricGroup(6)
sage: g = G((1, 2, 3, 4, 5, 6))
sage: c1 = conjugacy_class(g,G)
CPU time: 0.96 s, Wall time: 1.18 s

sage: %time
sage: G = SymmetricGroup(6)
sage: g = G((1, 2, 3, 4, 5, 6))
sage: c2 = conjugacy_class_gap(g,G)
CPU time: 0.05 s, Wall time: 0.08 s

stays so when the group gets larger:

sage: %time
sage: G = SymmetricGroup(7)
sage: g = G((1, 2, 3, 4, 5, 6))
sage: c1 = conjugacy_class(g,G)
CPU time: 6.99 s, Wall time: 8.45 s

sage: %time
sage: G = SymmetricGroup(7)
sage: g = G((1, 2, 3, 4, 5, 6))
sage: c2 = conjugacy_class_gap(g,G)
CPU time: 0.32 s, Wall time: 0.36 s

and for really large groups gets even bigger, in this case is over
100x faster (WARNING, the first test takes about 10min to complete):

sage: %time
sage: G = SymmetricGroup(9)
sage: g = G((1, 2, 3, 4, 5, 6))
sage: c1 = conjugacy_class(g,G)
CPU time: 529.72 s, Wall time: 618.07 s

sage: %time
sage: G = SymmetricGroup(9)
sage: g = G((1, 2, 3, 4, 5, 6))
sage: c2 = conjugacy_class_gap(g,G)
CPU time: 3.87 s, Wall time: 4.66 s

Observe that the two functions produce exactly the same object:

sage: c1 == c2
True


My question: would it be interesting to include the wrapper for the
GAP function in sage?

Cheers
Javier

[William Stein]

2009/12/3 javier <veng...@gmail.com>:

YES, definitely. We really should to have way more wrapping of GAP
capabilities than we currently have.

William

[Florent Hivert]

Dear Javier,

> > sage: def conjugacy_class(g,G):
> > ... � � � cc = Set([x*g*x^(-1) for x in G])
> > ... � � � return cc
> >
> > this feels very pythonic and works just fine, but is terribly
> > inefficient since it requires a lot of computations and stores in
> > memory an array of the whole size of the group G before deleting
> > duplicates. As GAP has a function for computing the conjugacy class of
> > an element, I decided to wrap it and compare it with the naive
> > implementation above, coming up with this:
> >
> > def conjugacy_class_gap(g,G):
> > ... � � � GG = G._gap_()
> > ... � � � gg = g._gap_()
> > ... � � � cc = GG.ConjugacyClass(gg).AsList().sage()
> > ... � � � return Set([G(x) for x in cc])
> >

> > My question: would it be interesting to include the wrapper for the
> > GAP function in sage?
>
> YES, definitely. We really should to have way more wrapping of GAP
> capabilities than we currently have.

+1 !

However, I thing it should be a method of the group:
G.conjugacy_class(g).
Or even of the element itself since it knows G as it's parent:
g.conjugacy_class()

def conjugacy_class(self):
GG = self.parent()._gap_()
gg = self._gap_()
cc = GG.ConjugacyClass(gg).AsList().sage()

return Set([G(x) for x in cc])

And finally for those groups who are not known to gap, the fallback
(sage-only) method should be in the category FiniteGroups to be inherited by
any group.

Cheers,

Florent

[kcrisman]

> And finally for those groups who are not known to gap, the fallback
> (sage-only) method should be in the category FiniteGroups to be inherited by
> any group.

Speaking of such groups, this is a bit mysterious (sometimes a
calculation will say to download the optional database, sometimes no
error message, if GAP can't do, say, a character table). Is there
some "master list" of groups GAP knows about?

- kcrisman

[javier]

Hi there,

On Dec 3, 5:08 pm, Florent Hivert <florent.hiv...@univ-rouen.fr>
wrote:

> However, I thing it should be a method of the group:
>    G.conjugacy_class(g).

that was my original idea, to keep it close to GAP original
definition.

> Or even of the element itself since it knows G as it's parent:
>    g.conjugacy_class()
>
> def conjugacy_class(self):
>      GG = self.parent()._gap_()
>      gg = self._gap_()
>      cc = GG.ConjugacyClass(gg).AsList().sage()
>      return Set([G(x) for x in cc])

This also makes sense. I don't really know which choice would be
better. Maybe having both, doing something like

def conjugacy_class(self):
G = self.parent()
return G.conjugacy_class(g)

does that sound reasonable or would it be better to stick just to one
of them?

> And finally for those groups who are not known to gap, the fallback
> (sage-only) method should be in the category FiniteGroups to be inherited by
> any group.

I hadn't thought of that. Since all the groups I used are defined as
permutation groups I never ran into trouble, but now that you mention
it I see that GAP function doesn't work for matrix groups:

sage: F = GF(5)
sage: gens = [matrix(F,2,[1,2, -1, 1]), matrix(F,2, [1,1, 0,1])]
sage: G = MatrixGroup(gens)
sage: g = G(matrix(F,2,[1,2, -1, 1]))
sage: conjugacy_class_gap(g,G)
Traceback (most recent call last):
...
NotImplementedError


So I guess the right thing to do is something like

sage: def conjugacy_class(g,G):
... try: # Try to use GAP function if defined

... GG = G._gap_()
... gg = g._gap_()
... cc = GG.ConjugacyClass(gg).AsList().sage()
... return Set([G(x) for x in cc])

... except NotImplementedError: # If GAP doesn´t work, use
naive method
... return Set([x*g*x^(-1) for x in G])

maybe with some added checks to deal with abelian groups (trivial
conjugacy classes) and not using the naive method on infinite groups.

In which file should the code be included?
$SAGE_ROOT/devel/sage/sage/generic.py or somewhere else?

Cheers
Javier

[Robert Bradshaw]

On Dec 3, 2009, at 10:04 AM, javier wrote:

> Hi there,
>
> On Dec 3, 5:08 pm, Florent Hivert <florent.hiv...@univ-rouen.fr>
> wrote:
>> However, I thing it should be a method of the group:
>> G.conjugacy_class(g).
>
> that was my original idea, to keep it close to GAP original
> definition.
>
>> Or even of the element itself since it knows G as it's parent:
>> g.conjugacy_class()
>>
>> def conjugacy_class(self):
>> GG = self.parent()._gap_()
>> gg = self._gap_()
>> cc = GG.ConjugacyClass(gg).AsList().sage()
>> return Set([G(x) for x in cc])
>
> This also makes sense. I don't really know which choice would be
> better. Maybe having both, doing something like
>
> def conjugacy_class(self):
> G = self.parent()
> return G.conjugacy_class(g)
>
> does that sound reasonable or would it be better to stick just to one
> of them?

Yes, that makes sense.

Almost certainly as a method on the Group object in sage/groups/
group.pyx

- Robert

[Rob Beezer]

On Dec 3, 7:09 am, javier <vengor...@gmail.com> wrote:
> My question: would it be interesting to include the wrapper for the
> GAP function in sage?

+1

There are places where Sage/GAP just give you one of something, when
you might want all of them, and it is simply conjugacy that will
produce them all. For small examples, in educational settings, the
time and memory constraints really are not a big issue.

(1) all subgroups, but now we just get conjugacy class representatives

and

(2) Sylow subgroups - one only

are the ones that come to mind right away. Thanks for your work on
conjugacy classes - it will be very useful.

Rob

[Alex Ghitza]

Hi Javier,

On Thu, Dec 03, 2009 at 11:03:43AM -0800, Robert Bradshaw wrote:
> On Dec 3, 2009, at 10:04 AM, javier wrote:
>
> > This also makes sense. I don't really know which choice would be
> > better. Maybe having both, doing something like
> >
> > def conjugacy_class(self):
> > G = self.parent()
> > return G.conjugacy_class(g)
> >
> > does that sound reasonable or would it be better to stick just to one
> > of them?
>

I think it's a good idea to write the code as a method for groups, and
then have a "wrapper" method for group elements that calls the group
method as you wrote above.

> >
> > In which file should the code be included?
> > $SAGE_ROOT/devel/sage/sage/generic.py or somewhere else?
>
> Almost certainly as a method on the Group object in sage/groups/
> group.pyx
>

Yes, have a look at sage/groups/group.pyx. It has a FiniteGroup
class, where I think you should put your main method (that's what
Florent said as well, I think).

For group elements, one possibility is to put the wrapper method in
the class MultiplicativeGroupElement in the file
sage/structure/element.pyx. You would probably want to do something

like

def conjugacy_class(self):
G = self.parent()

try:
return G.conjugacy_class(self)
except AttributeError:
raise NotImplementedError, "Computation of conjugacy classes not implemented for %s"%self


because some groups (e.g. infinite ones) won't have the method conjugacy_class().
If anybody thinks that element.pyx should not get cluttered with this
kind of thing, please say something!



Before you start editing files in the Sage library, have a look at

http://wiki.sagemath.org/MercurialQueues



Thanks for working on this, and as William said, we need to get more
GAP functionality exposed, so feel free to wrap more stuff!


Best,
Alex


--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/

[Florent Hivert]

> Yes, have a look at sage/groups/group.pyx. It has a FiniteGroup
> class, where I think you should put your main method (that's what
> Florent said as well, I think).

Yep ! This will probably needs some cleanup when we will merge categories with
the other generic stuff but I think this is the right place in the mean time.

> For group elements, one possibility is to put the wrapper method in
> the class MultiplicativeGroupElement in the file
> sage/structure/element.pyx. You would probably want to do something
> like
>
> def conjugacy_class(self):
> G = self.parent()
> try:
> return G.conjugacy_class(self)
> except AttributeError:
> raise NotImplementedError, "Computation of conjugacy classes not implemented for %s"%self
>
>
> because some groups (e.g. infinite ones) won't have the method conjugacy_class().
> If anybody thinks that element.pyx should not get cluttered with this
> kind of thing, please say something!

something :-)

Same remark as above...

Florent

[javier]

Hi all,

I have been working on this and after a while decided that my original
approach wasn't the most appropriate and started rewriting everything
for scratch.

After thinking about this problem making "conjugacy_class" a method
that returns a list (or set) didn't feel right. GAP has many methods
working on conjugacy classes, so the most natural thing to do should
be to create a sage/python class "ConjugacyClass" for conjugacy
classes, and wrap any desired GAP methods inside this class. Does this
sound fine?

I have some working code, including the definition of the class,
wrapping of several GAP functions, and some native python methods such
as list, set, iter, getitem, repr and so on, but before pushing it I
wanted to be sure this is the right approach.

I think within this new framework, the definition of the class
"ConjugacyClass" should go in the groups file (but don't know exactly
where!), and the G.conjugacy_class(g) method should be defined for all
groups, not only for finite, with the "set" and "list" methods
initially raising NotImplemented errors for infinite groups, but
giving room if somebody ever want to implement explicit descriptions
for some particular infinite groups (like f.i. FC-groups).

Is there anything I should take into account regarding the eventual
merge with the categories code?

Cheers
J

On Dec 3 2009, 10:15 pm, Florent Hivert <florent.hiv...@univ-rouen.fr>
wrote:

[Nick Alexander]

On 8-Jan-10, at 8:55 AM, javier wrote:

> Hi all,
>
> I have been working on this and after a while decided that my original
> approach wasn't the most appropriate and started rewriting everything
> for scratch.
>
> After thinking about this problem making "conjugacy_class" a method
> that returns a list (or set) didn't feel right. GAP has many methods
> working on conjugacy classes, so the most natural thing to do should
> be to create a sage/python class "ConjugacyClass" for conjugacy
> classes, and wrap any desired GAP methods inside this class. Does this
> sound fine?

I am not able to comment on this particular problem, but in general I
am a strong +1 to this approach.

Nick

[Simon King]

Hi all,

Yep, this makes a lot of sense to me as well.

By the way, is there any chance to create a "libGAP", i.e., a way to
avoid the pexpect interface, similar to what has been done in
libsingular?

Cheers,
Simon

[Mike Hansen]

On Fri, Jan 8, 2010 at 12:19 PM, Simon King <simon...@nuigalway.ie> wrote:
> By the way, is there any chance to create a "libGAP", i.e., a way to
> avoid the pexpect interface, similar to what has been done in
> libsingular?

See http://trac.sagemath.org/sage_trac/ticket/6391

--Mike

[David Joyner]

On Fri, Jan 8, 2010 at 11:55 AM, javier <veng...@gmail.com> wrote:
> Hi all,
>
> I have been working on this and after a while decided that my original
> approach wasn't the most appropriate and started rewriting everything
> for scratch.
>
> After thinking about this problem making "conjugacy_class" a method
> that returns a list (or set) didn't feel right. GAP has many methods
> working on conjugacy classes, so the most natural thing to do should
> be to create a sage/python class "ConjugacyClass" for conjugacy
> classes, and wrap any desired GAP methods inside this class. Does this
> sound fine?

This sounds fine, but if you are going to have a method
to compute representatives then your patch possibly should
involve modifying the conjugacy_classes_representatives
method in the perm_groups module. Also, for the
list method you might want to think about "@cached_method", as in the
list method for PermutationGroups in the perm_groups module.

>
> I have some working code, including the definition of the class,
> wrapping of several GAP functions, and some native python methods such
> as list, set, iter, getitem, repr and so on, but before pushing it I
> wanted to be sure this is the right approach.
>
> I think within this new framework, the definition of the class
> "ConjugacyClass" should go in the groups file (but don't know exactly
> where!), and the G.conjugacy_class(g) method should be defined for all
> groups, not only for finite, with the "set" and "list" methods
> initially raising NotImplemented errors for infinite groups, but
> giving room if somebody ever want to implement explicit descriptions
> for some particular infinite groups (like f.i. FC-groups).

I'm not sure where. Maybe a new module?

>
> Is there anything I should take into account regarding the eventual
> merge with the categories code?

I don't know. Hopefully someone else does.

Thanks for working on this!

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
>

[William Stein]

Yep. And moreover that is in some ways *easier* than libSingular was.
The sum total work on it so far was me for one week last summer at
Sage Days in Barcelona. Also, I had a student try to work on it last
quarter, but he didn't get anywhere (due to lack of necessary
background experience). However, I think finishing libgap enough to
use it is a reasonable project.

-- William

[javier]

Hi there,

I am trying to get my code moved to the source files, but am finding
some problems (it is my first time!). What I did was:
- cloning sage to my own branch (called sage-groups),
- Added a new file $SAGE_ROOT/devel/sage-groups/sage/groups/
group_conjugacy_class.py with my class code
- modified $SAGE_ROOT/devel/sage-groups/sage/groups/group.pyx
including this in the class Group:

def conjugacy_class(self, g):
"""
This function should go inside the Group class

INPUT:

- ``G`` - A group

- ``g``- An element of G

OUTPUT:

- The conjugacy class of g in G (as a ConjugacyClass object)

EXAMPLES:

::

sage: G = SymmetricGroup(4)
sage: g = G((1,2,3,4))
sage: conjugacy_class(G,g)
Conjugacy class of (1,2,3,4) in Symmetric group of order
4! as a permutation group

"""
from sage.groups.group_conjugacy_class import ConjugacyClass
as ConjugacyClass
return ConjugacyClass(self,g)

- modified the file all.py in the same folder by adding the line

from group_conjugacy_class import *

- build with sage -b

Then I try to test the code by running sage -t ..../
group_conjugacy_class.py and I get this:

sage -t "devel/sage-groups/sage/groups/group_conjugacy_class.py"
A mysterious error (perhaps a memory error?) occurred, which may have
crashed doctest.
[15.4 s]
exit code: 768

----------------------------------------------------------------------
The following tests failed:

sage -t "devel/sage-groups/sage/groups/
group_conjugacy_class.py"
Total time for all tests: 15.4 seconds

when I try to start sage I get this error at the new
group_conjugacy_class.py file
NameError: name 'cached_method' is not defined

I guess I am doing something stupid or forgetting to do something?

Cheers
J

[javier]

Sorted it out, I had forgotten to import one file. Sorry for the
noise. Class patches nicely now; I am just having some test failures
due to different orderings of some output sets. Is there a standard
way of implementing tests that involve sets as outputs?

In a related matter, in the _set_ method, is it better to return a
python set or a sage Set?

Cheers
J

[Dima Pasechnik]

[...]

> > And finally for those groups who are not known to gap, the fallback
> > (sage-only) method should be in the category FiniteGroups to be inherited by
> > any group.
>
> I hadn't thought of that. Since all the groups I used are defined as
> permutation groups I never ran into trouble, but now that you mention
> it I see that GAP function doesn't work for matrix groups:

No, that's not true. It must be a bug or a feature of Sage, not
something
that does not work in GAP. Here is the GAP session that does what
you tried below:

gap> a1:=Z(5)^0*[[1,2],[-1,-1]];
[ [ Z(5)^0, Z(5) ], [ Z(5)^2, Z(5)^2 ] ]
gap> a2:=Z(5)^0*[[1,1],[0,1]];
[ [ Z(5)^0, Z(5)^0 ], [ 0*Z(5), Z(5)^0 ] ]
gap> gg:=Group(a1,a2);
Group([ [ [ Z(5)^0, Z(5) ], [ Z(5)^2, Z(5)^2 ] ],
[ [ Z(5)^0, Z(5)^0 ], [ 0*Z(5), Z(5)^0 ] ] ])
gap> ConjugacyClass(gg,a1);
[ [ Z(5)^0, Z(5) ], [ Z(5)^2, Z(5)^2 ] ]^G

>
> sage: F = GF(5)
> sage: gens = [matrix(F,2,[1,2, -1, 1]), matrix(F,2, [1,1, 0,1])]
> sage: G = MatrixGroup(gens)
> sage: g = G(matrix(F,2,[1,2, -1, 1]))
> sage: conjugacy_class_gap(g,G)
> Traceback (most recent call last):
> ...
> NotImplementedError
>

[...]

HTH,
Dmitrii

[javier]

You are absolutely right, GAP deals perfectly with the conjugacy
classes of groups of matrices.
Apparently what is not implemented is the conversion of GAP matrices
back into sage matrices:

sage: F = GF(5)
sage: gens = [matrix(F,2,[1,2, -1, 1]), matrix(F,2, [1,1, 0,1])]
sage: G = MatrixGroup(gens)

sage: gg = g._gap_()
sage: ggg = gg.sage()
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call
last)

/Users/javier/<ipython console> in <module>()

/Applications/sage/local/lib/python2.6/site-packages/sage/interfaces/
expect.pyc in sage(self)
1657 Rational Field
1658 """
-> 1659 return self._sage_()
1660
1661 def __repr__(self):

/Applications/sage/local/lib/python2.6/site-packages/sage/interfaces/
expect.pyc in _sage_(self)
1643 return sage.misc.sage_eval.sage_eval
(self._sage_repr())
1644 except:
-> 1645 raise NotImplementedError
1646
1647

NotImplementedError:
sage: ggg = sage(gg)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)

/Users/javier/<ipython console> in <module>()

TypeError: 'module' object is not callable

It would be great having this conversion working, though...

Cheers
J

[William Stein]

On Sat, Jan 9, 2010 at 12:03 PM, Minh Nguyen <nguye...@gmail.com> wrote:
> Hi,

>
> On Sun, Jan 10, 2010 at 2:06 AM, javier <veng...@gmail.com> wrote:
>> Sorted it out, I had forgotten to import one file. Sorry for the
>> noise. Class patches nicely now; I am just having some test failures
>> due to different orderings of some output sets. Is there a standard
>> way of implementing tests that involve sets as outputs?
>

> You should be aware there is no fixed ordering when you output the
> elements of a set. This is especially important when you have the
> string representation of all elements of a set as expected output in a
> doctest. For example, on some platform a set consisting of the
> elements 1, 2, 3 might be output in a different order such as 3, 2, 1.
> If the elements of your set can be sorted in some standard order, it
> might be a good idea to first sort the elements, then have the sorted
> elements be expected output of a doctest. A similar issue applies when
> you have the values of a dictionary as expected output in a doctest.

>
>
>> In a related matter, in the _set_ method, is it better to return a
>> python set or a sage Set?
>

> I don't know how to answer this question without knowing the (updated)
> code or the context of the code.

I would vote for a Sage set.

William

[javier]

The implementation of the conjugacy classes is now ticket #7886:
http://sagetrac.org/sage_trac/ticket/7886

At the moment all the test pass except the one for _getitem_; since
the elements of the conjugacy class appear in a random order, I don't
know how to make a working test for that function. I went for Set
instead of set because the output looks better. I intend to wrap a few
more functions on that patch, if you have a favorite one you'd like to
see now is the time to tell!

Concerning Dmitri remark above, if there was a way to convert gap
matrices into sage matrices it could be possible to extend
conjugacy_classes_representatives (as well as conjugacy_classes) to
matrix groups. That would also make computation of conjugacy classes
for matrix groups several times faster by avoiding the naive fallback.
Should I open a different ticket for that?

Cheers
J

On Jan 9, 8:03 pm, Minh Nguyen <nguyenmi...@gmail.com> wrote:
> Hi,
>

> On Sun, Jan 10, 2010 at 2:06 AM, javier <vengor...@gmail.com> wrote:
> > Sorted it out, I had forgotten to import one file. Sorry for the
> > noise. Class patches nicely now; I am just having some test failures
> > due to different orderings of some output sets. Is there a standard
> > way of implementing tests that involve sets as outputs?
>

> You should be aware there is no fixed ordering when you output the
> elements of a set. This is especially important when you have the
> string representation of all elements of a set as expected output in a
> doctest. For example, on some platform a set consisting of the
> elements 1, 2, 3 might be output in a different order such as 3, 2, 1.
> If the elements of your set can be sorted in some standard order, it
> might be a good idea to first sort the elements, then have the sorted
> elements be expected output of a doctest. A similar issue applies when
> you have the values of a dictionary as expected output in a doctest.
>

> > In a related matter, in the _set_ method, is it better to return a
> > python set or a sage Set?
>

> I don't know how to answer this question without knowing the (updated)
> code or the context of the code.
>

> --
> Regards
> Minh Van Nguyen

[Simon King]

Hi Javier!

On 9 Jan., 23:01, javier <vengor...@gmail.com> wrote:
> The implementation of the conjugacy classes is now ticket #7886:http://sagetrac.org/sage_trac/ticket/7886
>
> At the moment all the test pass except the one for _getitem_; since
> the elements of the conjugacy class appear in a random order, I don't
> know how to make a working test for that function.

Yes, sets and dictionaries are not good for doc tests. AFAIK, the
method of choice is to transforme the output into a sorted list,
sage: sorted(Set([1,3,2]))
[1, 2, 3]
sage: sorted({3:2,1:5}.items())
[(1, 5), (3, 2)]

Thank you very much for working on it!
Simon

[Dima Pasechnik]

On Jan 10, 6:01 am, javier <vengor...@gmail.com> wrote:
[...]

> Concerning Dmitri remark above, if there was a way to convert gap
> matrices into sage matrices it could be possible to extend
> conjugacy_classes_representatives (as well as conjugacy_classes) to
> matrix groups. That would also make computation of conjugacy classes
> for matrix groups several times faster by avoiding the naive fallback.
> Should I open a different ticket for that?
>

from what I gather, it asks first of all for a consistent way to
handle GAP's field elements. A field can be finite, as here in this
thread, or, say, cyclotomic, as it would happen, e.g., when dealing
with character tables (or representations of finite groups over C).
And there seems to be no functionality whatsoever for this in Sage. Am
I correct?
Actually, I particularly badly need a way to convert GAP's cyclotomics
into Sage's data, so I might like to pick this up, although this would
be my very 1st Sage coding project, and I would need a lot of pointers
of how to start...

[...]

Dmitrii

[Alex Ghitza]

On Sat, 9 Jan 2010 21:35:31 -0800 (PST), Dima Pasechnik <dim...@gmail.com> wrote:
>
> from what I gather, it asks first of all for a consistent way to
> handle GAP's field elements. A field can be finite, as here in this
> thread, or, say, cyclotomic, as it would happen, e.g., when dealing
> with character tables (or representations of finite groups over C).
> And there seems to be no functionality whatsoever for this in Sage. Am
> I correct?

What is "this" in your sentence? Finite fields? Cyclotomic fields?
Both of these are definitely in Sage, have a look at

sage: FiniteField?

sage: CyclotomicField?

> Actually, I particularly badly need a way to convert GAP's cyclotomics
> into Sage's data, so I might like to pick this up, although this would
> be my very 1st Sage coding project, and I would need a lot of pointers
> of how to start...
>

You can start by having a look at interfaces/gap.py in the Sage library,
for instance at the GapElement class. You would want something like
this to work:

sage: a = gap('E(9)')
sage: a.sage()

At the moment, that raises a NotImplementedError.

You also want to look at the CyclotomicField class in
rings/number_field/number_field.py, more particularly at its __call__()
method which converts various things into elements of a cyclotomic
field.

I don't have time to give more details now, but it should help you to
start. Let us know how it's going!

[javier]

This is now Ticket #7890:
http://trac.sagemath.org/sage_trac/ticket/7890

Thanks for volunteering to work on this, Dmitri! It would be awesome
to be able to access all that gap functions from sage.
Skimming a bit at the conversion code, it looks like the function
"sage" is called on the gap string representing the gap object. A big
part of the problem seems to be deciding what to do with that string
(i.e. to what type of sage object is it converted). For instance if
you create a gap matrix (with integral coefficients) it gets converted
back into a list of lists and not into a sage matrix:

sage: A = gap([[1,2],[2,3]])
sage: A.IsMatrix()
true
sage: B = A.sage()
sage: B
[[1, 2], [2, 3]]
sage: type(B)
<type 'list'>

Maybe the best place to start is to look at any objects that can be
successfully converted back and forth and see what is going on there.

Cheers
J

On Jan 10, 7:43 am, Alex Ghitza <aghi...@gmail.com> wrote:

[David Joyner]

On Sun, Jan 10, 2010 at 6:04 AM, javier <veng...@gmail.com> wrote:
> This is now Ticket #7890:
> http://trac.sagemath.org/sage_trac/ticket/7890
>
> Thanks for volunteering to work on this, Dmitri! It would be awesome
> to be able to access all that gap functions from sage.
> Skimming a bit at the conversion code, it looks like the function
> "sage" is called on the gap string representing the gap object. A big
> part of the problem seems to be deciding what to do with that string
> (i.e. to what type of sage object is it converted). For instance if
> you create a gap matrix (with integral coefficients) it gets converted
> back into a list of lists and not into a sage matrix:
>
> sage: A = gap([[1,2],[2,3]])
> sage: A.IsMatrix()
> true
> sage: B = A.sage()
> sage: B
> [[1, 2], [2, 3]]
> sage: type(B)
> <type 'list'>
>
> Maybe the best place to start is to look at any objects that can be
> successfully converted back and forth and see what is going on there.

Some conversions of gap matrices into sage matrices over a finite field
is done in coding/guava.py. Another place to look is in
interfaces/gap.py.

[Simon King]

On 10 Jan., 12:04, javier <vengor...@gmail.com> wrote:
> This is now Ticket #7890:http://trac.sagemath.org/sage_trac/ticket/7890
>
> Thanks for volunteering to work on this, Dmitri! It would be awesome
> to be able to access all that gap functions from sage.
> Skimming a bit at the conversion code, it looks like the function
> "sage" is called on the gap string representing the gap object.

Well, that's a default method, i.e., if nothing else is implemented
than a conversion by strings is attempted, because there is some hope
that the result makes sense.

So, a proper way would be to override the default sage() method (from
pexpect, or where is it defined?) for the gap interface.

This new method would test the type of gap data (matrix; permutation
group element; conjugacy class, ...) and do whatever needs to be done
(return a sage matrix; return a permutation; return an instance of the
new "conjugacy class" class, ...). Only if an unknown data type
occurs, a string conversion would be attempted, as a last resort. If
it fails, then nothing can be done.

I don't know how to properly test the data type in gap. Would one use
functions like IsPermGroup, IsMatrix?

So, if IsMatrix is true for a gap object M, then the next step is to
determine the underlying ring (dunno how). If R is that ring, then
M.sage() would return a matrix over R.sage().

Best regards,
Simon

[Dima Pasechnik]

On Jan 10, 7:04 pm, javier <vengor...@gmail.com> wrote:
[...]

> For instance if
> you create a gap matrix (with integral coefficients)

well, there no "static type" matrices in GAP (well, unless you work
with, say, matrix Lie algebras, and have multiplication overloaded).
They are just lists of lists of right sizes, with entries in a common
ring.

I am surprised to hear that Sage is less flexible here (ok ,there
could be, say, special matrices, say, dense numeric
and bit matrices, that deserve a special treatment, but otherwise this
seems strange...)

> it gets converted
> back into a list of lists and not into a sage matrix:
>
> sage: A = gap([[1,2],[2,3]])
> sage: A.IsMatrix()
> true
> sage: B = A.sage()
> sage: B
> [[1, 2], [2, 3]]
> sage: type(B)
> <type 'list'>
>

so I'd rather see Sage becoming more GAP-like in this sense,
although I realise this may not happen soon or ever...

Dmitrii

[Simon King]

Hi Dima!

On 10 Jan., 13:47, Dima Pasechnik <dimp...@gmail.com> wrote:
> On Jan 10, 7:04 pm, javier <vengor...@gmail.com> wrote:
> well, there no "static type" matrices in GAP (well, unless you work
> with, say, matrix Lie algebras, and have multiplication overloaded).
> They are just lists of lists of right sizes, with entries in a common
> ring.
>
> I am surprised to hear that Sage is less flexible here

And I am surpised to hear that GAP has no proper matrices. Certainly a
matrix is MUCH more than a list of lists. For example, in order to
have a mathematical meaning, the marks of a matrix have to belong to
the same ring.

> (ok ,there
> could be, say, special matrices, say, dense numeric
> and bit matrices, that deserve a special treatment, but otherwise this
> seems strange...)

You seriously think that matrix multiplication, determinant, echelon
form etc. should be done with lists of lists? I doubt that this can be
any good. I acknowledge that GAP's main purpose is groups and not
linear algebra. But providing fast linear algebra is certainly an
objective of Sage.

What does all that mean for the sage() method of the GAP interface?

Do I understand correctly that IsMatrix just states that the object is
a list of lists of the same size?

Then, perhaps sage() could have an optional argument. For example, if
the user reckons that some GAP object L is formed by "matrices" (e.g.,
it is a list of lists of lists of the same size), then L.sage
(AsMatrix=True) would return a list of sage matrices, whereas L.sage()
would return a list of lists of lists.

But then, it would be challenging to make sage(AsMatrix=True) work for
a matrix of matrices...

Cheers,
Simon

[javier]

Hi Simon,

On Jan 10, 11:33 am, Simon King <simon.k...@nuigalway.ie> wrote:
> Well, that's a default method, i.e., if nothing else is implemented
> than a conversion by strings is attempted, because there is some hope
> that the result makes sense.
>
> So, a proper way would be to override the default sage() method (from
> pexpect, or where is it defined?) for the gap interface.

I think the method called is in interfaces/expect.pyc but I am not
sure about that.

> This new method would test the type of gap data (matrix; permutation
> group element; conjugacy class, ...) and do whatever needs to be done
> (return a sage matrix; return a permutation; return an instance of the
> new "conjugacy class" class, ...). Only if an unknown data type
> occurs, a string conversion would be attempted, as a last  resort. If
> it fails, then nothing can be done.

The problem, as I see it, is that AFAIK gap has no "type checking" to
tell what kind of object we are dealing with (if there really is such
a method, I'd love to be corrected!).

> I don't know how to properly test the data type in gap. Would one use
> functions like IsPermGroup, IsMatrix?
>
> So, if IsMatrix is true for a gap object M, then the next step is to
> determine the underlying ring (dunno how). If R is that ring, then
> M.sage() would return a matrix over R.sage().

For the particular case of matrices that might actually work. Since
gap's IsMatrix ensures that all the entries belong to a common ring
(beyond checking the lists have the right size) we only need to check
the base ring of one of the elements, for instance the [1,1], which is
always going to be there:

sage: h = matrix(GF(5),2,[1,2, -1, 1])
sage: hh = h._gap_()
sage: hh.IsMatrix()
true
sage: hh[1,1].Ring()
GF(5)

So, lacking a better choice we could just make a list of distinguished
objects in which to apply ad-hoc conversion methods.

Cheers
J

[Dima Pasechnik]

Hi Simon,

On Jan 10, 9:32 pm, Simon King <simon.k...@nuigalway.ie> wrote:
> Hi Dima!
>
> On 10 Jan., 13:47, Dima Pasechnik <dimp...@gmail.com> wrote:
>
> > On Jan 10, 7:04 pm, javier <vengor...@gmail.com> wrote:
> > well, there no "static type" matrices in GAP (well, unless you work
> > with, say, matrix Lie algebras, and have multiplication overloaded).
> > They are just lists of lists of right sizes, with entries in a common
> > ring.
>
> > I am surprised to hear that Sage is less flexible here
>
> And I am surpised to hear that GAP has no proper matrices. Certainly a
> matrix is MUCH more than a list of lists. For example, in order to
> have a mathematical meaning, the marks of a matrix have to belong to
> the same ring.

Actually, I mentioned that entries must be in a common ring for
IsMatrix to return true.

>
> > (ok ,there
> > could be, say, special matrices, say, dense numeric
> > and bit matrices, that deserve a special treatment, but otherwise this
> > seems strange...)
>
> You seriously think that matrix multiplication, determinant, echelon
> form etc. should be done with lists of lists?

No, I don't mean these *should* be, but
there is only a very small and tolerable loss in efficiency when the
matrix entries lie in
a ring with expensive arithmetic, e.g. cyclotomics, or a large finite
field of non-prime order,
or huge integers.
GAP has a special type of matrices with entries in a small finite
field, on which it operates
quite fast. (One can convert to these "fast" matrices explicitly (or
even implicitly?) when possible)

The advantage for a semi-interactive system is obvious - one does not
need to worry about the
particular matrix ring (if we talk about square matrices) when playing
with the data!
(I still recall how much grief an overtly typed system can give you,
from experience with CAYLEY in 1993 :-))

Actually, a similar point of view is taken when one works with
permutations - they need not be
confined to a fixed permutation group.

I somehow expected Sage to follow the GAP's suit here --- have slower
"dynamically typed"
matrices for all rings, and faster ones for specific "fast" rings and
"approximate rings", i.e. floating
point numbers.

And don't get me started on sparse matrices here. :-)

> I doubt that this can be
> any good. I acknowledge that GAP's main purpose is groups and not
> linear algebra. But providing fast linear algebra is certainly an
> objective of Sage.
>
> What does all that mean for the sage() method of the GAP interface?
>
> Do I understand correctly that IsMatrix just states that the object is
> a list of lists of the same size?

no, a bit more --- see above.

>
> Then, perhaps sage() could have an optional argument. For example, if
> the user reckons that some GAP object L is formed by "matrices" (e.g.,
> it is a list of lists of lists of the same size), then L.sage
> (AsMatrix=True) would return a list of sage matrices, whereas L.sage()
> would return a list of lists of lists.
>
> But then, it would be challenging to make sage(AsMatrix=True) work for
> a matrix of matrices...

From GAP's point of view, these are not matrices.
Actually, GAP is kinda weak on block matrices...

Dima
>
> Cheers,
> Simon

[javier]

Hi all,

have been hacking around a bit and finally got to this:

the class GapElement doesn't have a _sage_ method, when sage() is
called, it defers to the ExpectElement method, which is not aware of
the fact that we have a GAP object to start with. OTOH, I observed
there is a _matrix_ method that creates sage matrices when the ring is
provided and decided to build up from there.

So, I included a _sage_ method in the GapElement class in gap.py,
going like this:

def _sage_(self):
"""
Override of ExpectElement._sage_ method. Aiming for a better
conversion. Initially just for matrices!
"""
if self.IsMatrix():
ring = self[1,1].Ring().sage()
return self._matrix_(ring)
else: # If we don't know how to deal with this, return to
the default.
return ExpectElement._sage_(self)

after applying the patch one can do as follows:

sage: h = matrix(GF(5),2,[1,2, -1, 1])

sage: hh = gap(h)
sage: hh.sage()
[1 2]
[4 1]
sage: hh.sage() == h
True

So, it wasn't that hard (for matrices) after all. I don't know whether/
how this can be applied to the E(9) thing unless there is an
IsSomething gap method that can be used for them.

I'll prepare some doctests and upload a first patch.

Cheers
J

[Simon King]

Hi Javier!

On 10 Jan., 15:26, javier <vengor...@gmail.com> wrote:
> def _sage_(self):
>         """
>         Override of ExpectElement._sage_ method. Aiming for a better
> conversion. Initially just for matrices!
>         """
>         if self.IsMatrix():
>             ring = self[1,1].Ring().sage()
>             return self._matrix_(ring)
>         else:    # If we don't know how to deal with this, return to
> the default.
>             return ExpectElement._sage_(self)

Yep, this is what I meant.

Perhaps, for providing an additional layer of safety, one, might put
the "if" part in a try-except clause, such as

try:

if self.IsMatrix():
ring = self[1,1].Ring().sage()
return self._matrix_(ring)

except ...: # insert the expected kind of error to be catched
here
pass

# If we don't know how to deal with this, return to the
default.
return ExpectElement._sage_(self)

Cheers,
Simon

[Dima Pasechnik]

Javier,

[...]

>
> So, it wasn't that hard (for matrices) after all.

Good!

> I don't know whether/
> how this can be applied to the E(9) thing unless there is an
> IsSomething gap method that can be used for them.

Sure, there is
IsCyclotomic
and IsIntegralCyclotomic
for cyclotomics, resp., cyclotomic integers:

gap> IsIntegralCyclotomic(E(9));
true
gap> Field(E(9));
CF(9)

and

IsFFE for finite field elements:

gap> IsFFE(Z(5));
true
gap> Field(Z(5));
GF(5)

for more general fields and for rings it's also doable...

Cheers,
Dima

[John Cremona]

This is the way objects from the pari library are converted to Sage.
pari has an (imperfect) system of attributing types to objects, and
the conversion code branches on the value of its pari type, calling
suitable conversion code in each case.

So this seems like a sensible way to go for GAP conversion.

John

2010/1/10 Dima Pasechnik <dim...@gmail.com>:

[javier]

Patch submitted at
http://sagetrac.org/sage_trac/ticket/7890

the conversion of matrices only works when the conversion of the gap
ring works. In particular, it fails for cyclotomic fields, cyclotomic
rings, and finite fields of non-prime order. I have also modified the
_matrix_ method so that if no ring is given it tries to pick it up
from the first matrix entry.

To make this patch *really* useful conversion for all the missing
kinds of rings and fields should be implemented. For GF(p^x) the only
thing that needs to be done is to expand the p^x part (gap actually
returns something like "GF(2^4)" rather than "GF(16)" into a number
and then call the sage conversion specifying a generator name.

For cyclotomic and other kinds of fields some more work is needed.

Since GAP has two methods (Ring() and Field()) that are relevant here,
it would be great to have a way of deciding which one should be
called.

Any further work along these lines will be most welcome!

Cheers
J

[Dima Pasechnik]

Javier,

> def _sage_(self):
>         """
>         Override of ExpectElement._sage_ method. Aiming for a better
> conversion. Initially just for matrices!
>         """
>         if self.IsMatrix():
>             ring = self[1,1].Ring().sage()

This is not good enough. It could be that the [1,1]-element lies in a
proper subring.
One should either test each matrix entry and take the biggest ring, or
ask GAP to do it for you.
Say, if A is a GAP matrix you can do
gap> Field(Flat(A));
to get the smallest field containing all the entries of A.

>             return self._matrix_(ring)
>         else:    # If we don't know how to deal with this, return to
> the default.
>             return ExpectElement._sage_(self)
>

[...]

Dima

[Dima Pasechnik]

On Jan 11, 12:07 am, javier <vengor...@gmail.com> wrote:
> Patch submitted athttp://sagetrac.org/sage_trac/ticket/7890

>
> the conversion of matrices only works when the conversion of the gap
> ring works. In particular, it fails for cyclotomic fields, cyclotomic
> rings, and finite fields of non-prime order. I have also modified the
> _matrix_ method so that if no ring is given it tries to pick it up
> from the first matrix entry.
>
> To make this patch *really* useful conversion for all the missing
> kinds of rings and fields should be implemented. For GF(p^x) the only
> thing that needs to be done is to expand the p^x part (gap actually
> returns something like "GF(2^4)" rather than "GF(16)" into a number
> and then call the sage conversion specifying a generator name.

you can ask GAP to compute the size of the finite field:
gap> Size(Field(Z(2^4)));
16
and use it to set up the Sage field.

[javier]

Hi Dmitri,

On Jan 10, 5:48 pm, Dima Pasechnik <dimp...@gmail.com> wrote:
> This is not good enough. It could be that the [1,1]-element lies in a
> proper subring.
> One should either test each matrix entry and take the biggest ring, or
> ask GAP to do it for you.
> Say, if A is a GAP matrix you can do
> gap> Field(Flat(A));
> to get the smallest field containing all the entries of A.

Ouch. That is easily doable, but will slow down quite a bit my
conjugacy classes code.
Oh well, better get it slow now and look for a way of passing a global
ring around later on...
Anyway I think it's better to use Ring() rather than Field() since the
former can always be coerced into the latter.

As of now, this is what I have (including methods for finite and
cyclotomic fields). I don´t like all these nested if's so any
alternative proposal will be welcome...

def _sage_(self):
r"""

Override of ExpectElement._sage_ method. Aiming for a better
conversion. Initially just for matrices!

EXAMPLES:

- Conversion of gap matrices into sage matrices, back and
forth

::

sage: h = matrix(GF(5),2,[1,2, -1, 1])
sage: hh = gap(h)
sage: hh.sage()
[1 2]
[4 1]
sage: hh.sage() == h
True

- Conversion of finite fields into the corresponding sage
fields

::

sage: R = gap("GF(16)")
sage: R.sage()
Finite Field in x16 of size 2^4

- Conversion of cyclotomic fields

::

sage: K = gap("CF(9)")
sage: K.sage()
Cyclotomic Field of order 9 and degree 6

"""
try:
if self.IsMatrix(): # Conversion of matrices
return self._matrix_()
if self.IsRing(): # Conversion of rings
if self.IsField(): # Fields
if self.IsFinite(): # Finite fields
from sage.rings.finite_field import GF
size = self.Size()
var = 'x'+str(size)
return GF(size, var) # What is the right
thing to use as generator name??
if self.IsCyclotomicField(): # Cyclotomic
fields
# Don't know if there is a gap way of getting
the number n for CF(n), so use the defining string "CF(n)" instead.
# The following strips the first three
characters, that should be "C", "F", "(" and the last ")".
from sage.rings.number_field.number_field
import CyclotomicField
n = int(str(self)[3:-1])
return CyclotomicField(n)
except NotImplementedError:
pass
return ExpectElement._sage_(self)

Is there a canonical or preferred way of calling the generator of GF
(q)? I went for "xq" (where q is a prime power) but that can easily
been changed.

The code for determining the ring has been replaced by

R = self.Flat().Ring().sage()

and moved to the _matrix_ method in the same class.

Cheers
J

[Simon King]

On 10 Jan., 19:39, javier <vengor...@gmail.com> wrote:
> Is there a canonical or preferred way of calling the generator of GF
> (q)? I went for "xq" (where q is a prime power) but that can easily
> been changed.

Is it possible to chose take the same name that GAP uses?

Cheers,
Simon

[javier]

Hi Simon,

On Jan 10, 7:57 pm, Simon King <simon.k...@nuigalway.ie> wrote:
> Is it possible to chose take the same name that GAP uses?

In GAP the generator of (the multiplicative group of) say GF(16) is
called "Z(2^4)", so I guess the answer is no, we cannot use GAP name.
We can go for something like Z16, or z_16 or anything like that.

I have been trying some code to convert elements of gap finite fields
into the corresponding elements of sage finite fields. The sort of
straightforward manner fails because of this behavior:

sage: a = gap("Z(2^4)")
sage: a^5
Z(2^2)

and apparently sage has no way of coercing finite fields into bigger
finite fields (in this example a coercion map from GF(4) to GF(16)
would send z4 to z16^5):

sage: A = GF(4, "z4")
sage: B = GF(16, "z16")
sage: x = A.gen()
sage: B(x)

---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)

/Users/javier/<ipython console> in <module>()

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/
finite_field_givaro.so in
sage.rings.finite_field_givaro.FiniteField_givaro.__call__ (sage/rings/
finite_field_givaro.cpp:4466)()

TypeError: unable to coerce from a finite field other than the prime
subfield

I can find a way around this by parsing the GAP strings with a lot of
care, but that is going to be an ugly piece of code and I'd rather
avoid it. Is there an easy way of getting the coercion maps for finite
fields, or maybe a way of regularizing the GAP output so that
everything is written in terms of the generator?

Cheers
J

[Dima Pasechnik]

On Jan 11, 7:19 am, javier <vengor...@gmail.com> wrote:
[...]

> I have been trying some code to convert elements of gap finite fields
> into the corresponding elements of sage finite fields. The sort of
> straightforward manner fails because of this behavior:
>
> sage: a = gap("Z(2^4)")
> sage: a^5
> Z(2^2)
>
> and apparently sage has no way of coercing finite fields into bigger
> finite fields (in this example a coercion map from GF(4) to GF(16)
> would send z4 to z16^5):

[...]

> TypeError: unable to coerce from a finite field other than the prime
> subfield

I reckon this must be due to Sage representing the finite field of
order p^n
as quotient rings F_p[x]/(f(x)), with f an irreducible polynomial of
degree n. Indeed, in this case to do the coercion to, say F_{p^m}=F_p
[x]/(g(x)), (with n dividing m, of course) would require some
nontrivial (and slow) polynomial arithmetic, unless f and g are
somehow "related".

GAP does it in a more clever way, at least for its "standard" finite
fields; f and g are always related in such a way that such a
computation is trivial. Namely, the primitive element Z(p^n) of the
1st field equals Z(p^m)^((p^m-1)/(p^n-1)), where Z(p^m) is the
primitive element of the 2nd field.

>
>  I can find a way around this by parsing the GAP strings with a lot of
> care, but that is going to be an ugly piece of code and I'd rather
> avoid it. Is there an easy way of getting the coercion maps for finite
> fields, or maybe a way of regularizing the GAP output so that
> everything is written in terms of the generator?

for the latter, hopefully the remark above is useful.

Dmitrii
>
> Cheers
> J

[javier]

Hi Dima,

On Jan 11, 4:14 am, Dima Pasechnik <dimp...@gmail.com> wrote:
> I reckon this must be due to Sage representing the finite field of
> order p^n
> as quotient rings F_p[x]/(f(x)), with f an irreducible polynomial of
> degree n. Indeed, in this case to do the coercion to, say F_{p^m}=F_p
> [x]/(g(x)), (with n dividing m, of course) would require some
> nontrivial (and slow) polynomial arithmetic, unless f and g are
> somehow "related".

I am afraid I don't know the details on how finite fields are
implemented in sage

> GAPdoes it in a more clever way, at least for its "standard" finite

> fields; f and g are always related in such a way that such a
> computation is trivial. Namely, the primitive element Z(p^n) of the
> 1st field equals Z(p^m)^((p^m-1)/(p^n-1)), where Z(p^m) is the
> primitive element of the 2nd field.

The generators in GAP are the roots of Conway polynomials, right?
IIRC, the map taking z_r into (z_s)^((s-1)/(r-1)) defines a field
morphism no matter which generator of the multiplicative groups you
take. Of course the problem is that this morphism is not canonical
(and thus doesn't provide a functorial construction).

Anyhoo, back to the point in case, what you propose is similar to what
I had originally in mind. The problem is how to obtain the original
value of "p^m". In the example mentioned before one has

sage: b = gap("Z(2^4)^5")
sage: b
Z(2^2)
sage: b.Field()
GF(2^2)

so, b was initially defined as an element of GF(16), but GAP standard
form forgets about it and considers it an element of GF(4). I don't
see any way out of this, so it looks like the only reasonable sage()
method cannot return anything but an element of sage's GF(4), as there
is no way to know what the original field of definition was. I already
have some code that does this and works _almost_ fine, the only
(partially related) problem being converting Z(q) into the sage
generator of GF(q) only works if q is _not_ a prime, because by
default GF(p) returns "1" as its generator, rather than a primitive
element.

sage: K = GF(5)
sage: K.gen()
1

Is there any rationale for that or is it the result of a particular
implementation?

A possible way out of this situation I see making an optional
implementation of finite fields using Conway polynomials so that
coercion maps can be built in. I am not sure I have the skills to do
that myself. Any number theorist, out there?

I will try to give a look to cenverting elements of cyclotomic fields
this evening when I get home. Hopefully that should be easier since
coercion for cyclotomic fields is very well behaved. For what respects
elements of finite fields, I am afraid I am out of ideas here, so any
suggestions or anyone volunteering to jump in would be greatly
appreciated.

Cheers
J

[John Cremona]

I haven't time right now to go through the different finite field
types in Sage, but not that Conway polynomials are not known (as far
as I know) for all combinations of characteristic and degree, so they
give a good solution for some (common) cases but not all.

Many of us would dearly like to be able to coerce from GF(p^n) to
GF(p^m) when n|m but n>1.

John

2010/1/11 javier <veng...@gmail.com>:

[Dima Pasechnik]

John,

On Jan 11, 10:24 pm, javier <vengor...@gmail.com> wrote:
> Hi Dima,
>
> On Jan 11, 4:14 am, Dima Pasechnik <dimp...@gmail.com> wrote:
>
> > I reckon this must be due to Sage representing the finite field of
> > order p^n
> > as quotient rings F_p[x]/(f(x)), with f an irreducible polynomial of
> > degree n. Indeed, in this case to do the coercion to, say F_{p^m}=F_p
> > [x]/(g(x)), (with n dividing m, of course) would require some
> > nontrivial (and slow) polynomial arithmetic, unless f and g are
> > somehow "related".
>
> I am afraid I don't know the details on how finite fields are
> implemented in sage
>
> > GAPdoes it in a more clever way, at least for its "standard" finite
> > fields; f and g are always related in such a way that such a
> > computation is trivial. Namely, the primitive element Z(p^n) of the
> > 1st field equals Z(p^m)^((p^m-1)/(p^n-1)), where Z(p^m) is the
> > primitive element of the 2nd field.
>
> The generators in GAP are the roots of Conway polynomials, right?

yes.

> IIRC, the map taking z_r into (z_s)^((s-1)/(r-1)) defines a field
> morphism no matter which generator of the multiplicative groups you
> take. Of course the problem is that this morphism is not canonical
> (and thus doesn't provide a functorial construction).

exactly.

>
> Anyhoo, back to the point in case, what you propose is similar to what
> I had originally in mind. The problem is how to obtain the original
> value of "p^m". In the example mentioned before one has
>
> sage: b = gap("Z(2^4)^5")
> sage: b
> Z(2^2)
> sage: b.Field()
> GF(2^2)
>
> so, b was initially defined as an element of GF(16), but GAP standard
> form forgets about it and considers it an element of GF(4).

no, from GAP's point of view, Z(2^4)^5 is an element of GF(4).
And thus b is such an element, too...

> I don't
> see any way out of this, so it looks like the only reasonable sage()
> method cannot return anything but an element of sage's GF(4), as there
> is no way to know what the original field of definition was.

there is no way to define a canonical lifting to a bigger field,
unless
you restict yourself to the GAP's universe of Z(q)'s...

[Dima Pasechnik]

On Jan 11, 11:04 pm, Dima Pasechnik <dimp...@gmail.com> wrote:
> John,
oops, I meant Javier

[Jason Grout]

Two comments. First of all, we can deal with matrices of matrices,
though it isn't as natural as I had hoped. Here's the first thing that
I tried:

sage: mm=matrix(MatrixSpace(ZZ,2),2)
sage: mm[0]
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)

/home/grout/.sage/temp/tiny/2005/_home_grout__sage_init_sage_0.py in
<module>()

/home/grout/sage/local/lib/python2.6/site-packages/sage/matrix/matrix0.so
in sage.matrix.matrix0.Matrix.__getitem__ (sage/matrix/matrix0.c:5314)()

/home/grout/sage/local/lib/python2.6/site-packages/sage/matrix/matrix1.so
in sage.matrix.matrix1.Matrix.row (sage/matrix/matrix1.c:7428)()

/home/grout/sage/local/lib/python2.6/site-packages/sage/structure/factory.so
in sage.structure.factory.UniqueFactory.__call__
(sage/structure/factory.c:919)()

/home/grout/sage/local/lib/python2.6/site-packages/sage/structure/factory.so
in sage.structure.factory.UniqueFactory.get_object
(sage/structure/factory.c:1125)()

/home/grout/sage/local/lib/python2.6/site-packages/sage/modules/free_module.pyc
in create_object(self, version, key)
343 raise TypeError, "Argument sparse (= %s) must be
True or False" % sparse
344
--> 345 if not base_ring.is_commutative():
346 raise TypeError, "The base_ring must be a
commutative ring."
347

AttributeError: 'MatrixSpace_generic' object has no attribute
'is_commutative'

Since we can create a matrix of matrices appropriately, maybe we can fix
up a few things to make it make sense?

But there's also another way to get the "dynamically typed" matrices
through the generality of the symbolic ring. Here, I create a symbolic
matrix. Since symbolic objects wrap any other objects, I set the first
element of the matrix to a 2x2 identity matrix, and another element to a
real number. Printing is a little messed up, but you can see it's doing
the right thing here.

sage: mmsr=matrix(SR,2)
sage: mmsr[0,0]=SR(matrix(ZZ,2,2,1))
sage: mmsr
[[1 0]
[0 1] 0]
[ 0 0]
sage: mmsr[0,0]
[1 0]
[0 1]
sage: mmsr[0,1]=RR(e)
sage: mmsr
[ [1 0]
[0 1] 2.71828182845905]
[ 0 0]
sage: mmsr[0,0]
[1 0]
[0 1]
sage: mmsr[0,1]
2.71828182845905

Thanks,

Jason

[javier]

Dima,

On Jan 11, 3:04 pm, Dima Pasechnik <dimp...@gmail.com> wrote:
> no, from GAP's point of view, Z(2^4)^5 is an element of GF(4).
> And thus b is such an element, too...

then from the "gap-to-sage" point of view nothing else can be done. A
coercion between finite fields is needed before this method can work
in a completely satisfactory way. On a brighter note, I have solved
the problem with the conversion of elements in GF(p) with p prime, but
we'll have to deal with outputs belonging to different fields until
somebody else comes up with a better idea.

> there is no way to define a canonical lifting to a bigger field,
> unless
> you restict yourself to the GAP's universe of Z(q)'s...

As long as we only want to make computations (and not anything
functorial) and are looking at GF's as "abstract finite fields", would
it be enough having the noncanonical coercion defined in the
generators (whatever they are) as we talked? Or would that be pure
nonsense?

> > I will try to give a look to cenverting elements of cyclotomic fields
> > this evening when I get home. Hopefully that should be easier since
> > coercion for cyclotomic fields is very well behaved.

I have some almost working code here (this goes inisde the big
function):

if self.IsCyclotomic(): # Elements of cyclotomic fields
l = str(self)
l = l.replace("E", "CyclotomicField")
l = l.replace(")", ").gen()")
from sage.misc.sage_eval import sage_eval
return sage_eval(l)

the first three lines convert a typical string describing a cyclotomic
element in gap, like
"-E(9)^4-E(9)^7"
into the sage callable string describing the same element:
"-CyclotomicField(9).gen()^4-CyclotomicField(9).gen()^7"
and then return the result of sage evaluating this string.

Surely some regular expressions whiz can find a fancier way of doing
the above (hint, hint!) but for now this seems to work.

I have uploaded the code to
http://sagetrac.org/sage_trac/ticket/7890

Dima, can you test if this satisfies your needs for cyclotomic
elements?

Cheers
J

[William Stein]

On Mon, Jan 11, 2010 at 4:16 PM, javier <veng...@gmail.com> wrote:
> Dima,
>
> On Jan 11, 3:04 pm, Dima Pasechnik <dimp...@gmail.com> wrote:
>> no, from GAP's point of view, Z(2^4)^5 is an element of GF(4).
>> And thus b is such an element, too...
>
> then from the "gap-to-sage" point of view nothing else can be done. A
> coercion between finite fields is needed before this method can work
> in a completely satisfactory way. On a brighter note, I have solved
> the problem with the conversion of elements in GF(p) with p prime, but
> we'll have to deal with outputs belonging to different fields until
> somebody else comes up with a better idea.

Dumb question. There is code in Sage already to convert from GAP's
GF(p) (or GF(q)) to Sage's:

For a prime field:

sage: a = gap('Z(7)^3')
sage: GF(7)(a)
6

For a non-prime finite field:
sage: a = gap('Z(7^2)^2')
sage: a
Z(7^2)^2
sage: a^48
Z(7)^0
sage: k.<b> = GF(49)
sage: k(a)
b + 4

If you do k.__call__?? at this point, you'll see source. Following that you get

sage: sage.interfaces.gap.gfq_gap_to_sage??

So is all this discussion about re-implementing that function? What
are you doing that is better?

William

[javier]

Hi William,

On Jan 12, 12:24 am, William Stein <wst...@gmail.com> wrote:
> Dumb question.  There is code in Sage already to convert from GAP's
> GF(p) (or GF(q)) to Sage's:

you are completely right. Since at the beginning I tried to do
something like

sage: a = gap("Z(7)")
sage: a.sage()

and that didn't work I assumed that everything needed to be
reimplemented from scratch. Indeed the only thing that needed
implementation was the conversion of GAP finite fields into sage ones
for non-prime fields and cyclotomic fields. I have rewritten the
function wrapping those methods and putting everything together in a
single patch.

Sorry for wasting so much of everybody's time with this discussion. At
least now conversion of cyclotomic elements should work seamlessly.

Cheers
J

[William Stein]

On Mon, Jan 11, 2010 at 4:46 PM, javier <veng...@gmail.com> wrote:
> Hi William,
>
> On Jan 12, 12:24 am, William Stein <wst...@gmail.com> wrote:
>> Dumb question.  There is code in Sage already to convert from GAP's
>> GF(p) (or GF(q)) to Sage's:
>
> you are completely right. Since at the beginning I tried to do
> something like
>
> sage: a = gap("Z(7)")
> sage: a.sage()
>
> and that didn't work I assumed that everything needed to be
> reimplemented from scratch. Indeed the only thing that needed
> implementation was the conversion of GAP finite fields into sage ones
> for non-prime fields and cyclotomic fields.

Isn't the case of non-prime fields also already in Sage? It was in my example.

> I have rewritten the
> function wrapping those methods and putting everything together in a
> single patch.
>
> Sorry for wasting so much of everybody's time with this discussion. At
> least now conversion of cyclotomic elements should work seamlessly.

Excellent. Many thanks for adding cyclotomic elements. I hope you'll
continue to improve the Sage <--> GAP interface. There are also
people working on making a (very similar) C library version, which
will mean that any work you do on this will eventually get a big speed
boost.

William

>
> Cheers
> J
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[javier]

On Jan 12, 12:47 am, William Stein <wst...@gmail.com> wrote:
> Isn't the case of non-prime fields also already in Sage?  It was in my example.

The __call__ function for a non-prime field yes, was already defined.
What wasn't was the conversion of a gap non-prime field into a sage
prime field. Something like

sage: K = gap("GF(16)")
sage: K.sage()

didn't work before (because in gap there is no need to specify the
generator name), and that prevented doing automatic conversion of gap
finite field elements into sage finite field elements. The problem
with cyclotomic elements was something similar (there wasn't a sage()
method defined for gap cyclotomic fields).

> Excellent. Many thanks for adding cyclotomic elements.  I hope you'll
> continue to improve the Sage <--> GAP interface.  There are also
> people working on making a (very similar) C library version, which
> will mean that any work you do on this will eventually get a big speed
> boost.

That's awesome! Hope it arrives soon! :-D

Cheers
J

[John Cremona]

2010/1/12 javier <veng...@gmail.com>:

> On Jan 12, 12:47 am, William Stein <wst...@gmail.com> wrote:
>> Isn't the case of non-prime fields also already in Sage?  It was in my example.
>
> The __call__ function for a non-prime field yes, was already defined.
> What wasn't was the conversion of a gap non-prime field into a sage
> prime field. Something like
>
> sage: K = gap("GF(16)")
> sage: K.sage()
>
> didn't work before (because in gap there is no need to specify the
> generator name), and that prevented doing automatic conversion of gap
> finite field elements into sage finite field elements. The problem

I would find it convenient if in Sage itself, you could construct
GF(q) with q a non-prime without having to think of a name, by the
simple expedient of having Sage invent a name (such as aq, i.e. a256
if q=256, or perhaps a_p_e if q=p^e, so for q=256 it would be a_2_8).
This would just be a default, teh user could give their own name, so
no old code would break and the problem you raised would do away.

John

> with cyclotomic elements was something similar (there wasn't a sage()
> method defined for gap cyclotomic fields).
>
>> Excellent. Many thanks for adding cyclotomic elements.  I hope you'll
>> continue to improve the Sage <--> GAP interface.  There are also
>> people working on making a (very similar) C library version, which
>> will mean that any work you do on this will eventually get a big speed
>> boost.
>
> That's awesome! Hope it arrives soon! :-D
>
> Cheers
> J
>

[Nicolas M. Thiery]

Dear Javier,

On Sat, Jan 09, 2010 at 02:01:07PM -0800, javier wrote:
> The implementation of the conjugacy classes is now ticket #7886:
> http://sagetrac.org/sage_trac/ticket/7886

I went through your patch, and am definitely +1 on the overall design
and user interface! Here are some suggestions for categorifying the
internals:

Split the ConjugacyClass into two classes (in the same module as before):

class ConjucacyClass(Parent):
# A parent, in the FiniteEnumeratedSets() category
# (see FiniteEnumeratedSets().example())
# Generic implementation with naive algorithm(s)

class ConjugacyClassGap(ConjugacyClass):
# Specializes the relevant methods of the above by calling GAP

In sage.categories.finite_groups.FiniteGroups, put in ParentMethods
the conjugacy class method for groups:

def conjugacy_class(self, g)
return ConjugacyClass(self, g)

and in ElementMethods the conjugacy class method for group elements:

def conjugacy_class(self):
return self.parent().conjugacy_class(self)

And finally, in those Sage groups which are implemented as GAP groups
(that is matrix and permutation groups), and only for those, override
the default method by:

def conjugacy_class(self, g)
return ConjugacyClassGAP(self, g)

Being in FiniteEnumeratedSets will give you for free some default
methods (like ``cardinality`` implemented by default in terms of
``list``), as well as sanity checks between
list/iter/cardinality/... when calling ``TestSuite(c).run()``.

It will be easy to later extend this to infinite groups when there
will be a concrete need/implementation.

By the way, a related feature which could afford a similar design, and
that would be useful in the short run for my PhD student would be:

sage: G = PermutationGroup(...)
sage: for C in G.conjugacy_classes():
... ... C.cardinality() ... C.representative() ...

I'd be happy to review it (and the above), should you feel like
working on it :-)

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/