a problem in the new permutation groups code (and a solution ?)

[Dima Pasechnik]

While working on http://trac.sagemath.org/sage_trac/ticket/14291, it
came to my attention that one can now have permutation groups acting
on quite arbitrary domains (the only requirement for the domain elements
seems to be them being hashable).

This leads to the following kind of confusing situations:
suppose our permutation group G acts on, say, (1,2,3,4,(1,2),(2,3)).
Then things like "the orbit (1,2) under G" can be interpreted in two
different incompatible ways:
* the images under G of the pair of domain elements 1 and 2.
* the images under G of of the domain element (1,2).

I can see two ways to remedy this:
1) a framework with parents, etc
2) "boxing" the most "primitive" elements of the domain, i.e.
as in our example, using ((1),(2),(3),(4),(1,2),(2,3)) instead of
(1,2,3,4,(1,2),(2,3)); then certainly ((1),(2)) and (1,2) are
different things, problem solved.

(and certainly you can tell me that actually it's OK as it is... :))

IMHO, 2) is relatively easy to put into place, and 1) is tricky and quite a bit of
work.

Dima

[Benjamin Jones]

It seems to me that the ambiguity arises from the original statement, "the orbit (1,2) under G", not the fact that the domain is non-homogeneous. It's less ambiguous to say directly G.{1, 2} (the orbit of the _element_ {1, 2}) versus G.1 \union G.2 (the orbit of the subset {1, 2}). Then, which group action you are talking about is clear.

For the API, it seems best (to me) to have the standard orbit function (which takes an element of the domain and returns its orbit) and add to that an optional parameter which changes the semantics to orbits of sets. The user would have to supply a subset of the domain then, instead of an element or you'd raise a TypeError.

[Nils Bruin]

On Mar 21, 9:05 am, Benjamin Jones <benjaminfjo...@gmail.com> wrote:
> It seems to me that the ambiguity arises from the original statement,

Systems like magma (and I assume gap as well) solve this by having a
"GSet" type. If you have S3 acting on the GSet V={1,2,3} then, one can
construct the powerset W of V as a GSet as well. In that context there
is a natural distinction between the subset {1,2,3} of V (which is a
sub-GSet) and the element {1,2,3} of W.

One can talk about the orbit of the element {1,2} in W under S3 but
obviously, {1,2} is not a sub-GSet of V.

How these things coerce between each other is another matter, but I
suspect making such distinctions internally is unavoidable.

[Dima Pasechnik]

On 2013-03-21, Benjamin Jones <benjami...@gmail.com> wrote:
> --f46d0444e849ed15b904d871801a
> Content-Type: text/plain; charset=ISO-8859-1

>
> It seems to me that the ambiguity arises from the original statement, "the
> orbit (1,2) under G", not the fact that the domain is non-homogeneous. It's
> less ambiguous to say directly G.{1, 2} (the orbit of the _element_ {1, 2})
> versus G.1 \union G.2 (the orbit of the subset {1, 2}). Then, which group
> action you are talking about is clear.
>
> For the API, it seems best (to me) to have the standard orbit function
> (which takes an element of the domain and returns its orbit) and add to
> that an optional parameter which changes the semantics to orbits of sets.

in my example, {1,2} (the domain element) is naturally a subset of the domain, so in both
cases it's an orbit on subsets. The trouble is that it's not
well-defined for a domain like this.

[Dima Pasechnik]

On 2013-03-21, Nils Bruin <nbr...@sfu.ca> wrote:
> On Mar 21, 9:05 am, Benjamin Jones <benjaminfjo...@gmail.com> wrote:
>> It seems to me that the ambiguity arises from the original statement,
>
> Systems like magma (and I assume gap as well) solve this by having a
> "GSet" type. If you have S3 acting on the GSet V={1,2,3} then, one can
> construct the powerset W of V as a GSet as well. In that context there
> is a natural distinction between the subset {1,2,3} of V (which is a
> sub-GSet) and the element {1,2,3} of W.

On GAP there is nothing like GSet.
As far as I know, one needs to do that "boxing" trick
I explained there, too, if one needs to "mix" things in the domain of the
group.

>
> One can talk about the orbit of the element {1,2} in W under S3 but
> obviously, {1,2} is not a sub-GSet of V.
>
> How these things coerce between each other is another matter, but I
> suspect making such distinctions internally is unavoidable.

Many years ago I abandoned Magma's predecessor, Cayley, for GAP, as
Cayley's lack of proper coersions/conversions drove me insane all the time.

Dima

[Volker Braun]

I think its unambiguous to define the orbit of x recursively as 

1. use the action on domain elements if x is a domain element

2. otherwise, assume that the x is a list/set/... of domain elements

[Nathann Cohen]

Helloooooooooooooo !!!

> I think its unambiguous to define the orbit of x recursively as
> 1. use the action on domain elements if x is a domain element
> 2. otherwise, assume that the x is a list/set/... of domain elements

Well. It is when you know what you are doing and work on a spcific group.

When you write a Sage method, though, it is embarassing if you do not know wheter the orbit of a pair of elements is a set of element (input considered as element) or a set of pairs of elements (input considered as a se of elements).

Really there is no problem with this patch except that Dima does not like that the elements of a group could be things like 1,2,{1,2}, which makes {1,2} ambiguous (element? set of two elements?) ... What we did before is guess the type of INPUT according to a keyword named "action" (that we need anyway, if only to differentiate between OnTuples and OnSets) and everything works fine....

Nathann

[Nathann Cohen]

And PLEASE if you answer this thread please also send your answer to sage-devel, not only sage-combinat.

Nathann

[Volker Braun]

On Friday, March 22, 2013 2:51:05 PM UTC+1, Nathann Cohen wrote:

> I think its unambiguous to define the orbit of x recursively as
> 1. use the action on domain elements if x is a domain element
> 2. otherwise, assume that the x is a list/set/... of domain elements
Well. It is when you know what you are doing and work on a spcific group.

For non-interactive you either perform argument validation yourself or use the optional parameter G.orbit(foo, action='OnTuples').

[Nathann Cohen]

> For non-interactive you either perform argument validation yourself or use
> the optional parameter G.orbit(foo, action='OnTuples').

Oh. Ok, this is fine !

So Dima, do we guess the value of action when it is set to None, then translate the output according to the value of "action" ? That's a good answer !

Nathann

[Nathann Cohen]

> Would Evariste Galois raise from his grave and chase the designer
> of this?

I answered on the ticket, and said that I would help him if he did. But Dima you know that this thing will take ime if somebody actually ends up doing it and it's not related to this ticket. Why do you want to block it over that ?

Nathann

[Nathann Cohen]

> as I explained, the code you don't like there (cause it does not work on
> insane inputs) would work fine on sane inputs. And the uglier code you
> prefer would break things on insane inputs, too, although at some other
> point, e.g. at the one I outlined above in this thread.

It does not break things on insane input -- let's decide where we discuss this, I just answered that on the ticket -- for you are (from Sage's point of view) perfectly aware of what you are doing when you intersect :
- The orbit of a vertex which you obtained by doing g.action( x, action = "OnPoints" )
- The orbit of an edge which you obtained by doing g.action( (x,y), action = "OnSets")

Hence you KNOW that you are intersecting things of different types. We might as well say that the output of g.action( x, action = "OnPoints" ) is of type "OrbitOfPoint" and g.action( (x,y), action = "OnSets") of type "OrbitOfSet". You actually know this information because you filled the "action" argument yourself. You can infer the type of what is being returned just from the value of "action".

Nathann

[Dima Pasechnik]

On 2013-03-22, Nathann Cohen <nathan...@gmail.com> wrote:
> --bcaec52e66033a8d1704d88510dc
> Content-Type: text/plain; charset=ISO-8859-1

>
>> as I explained, the code you don't like there (cause it does not work on
>> insane inputs) would work fine on sane inputs. And the uglier code you
>> prefer would break things on insane inputs, too, although at some other
>> point, e.g. at the one I outlined above in this thread.
>
> It does not break things on insane input -- let's decide where we discuss
> this, I just answered that on the ticket -- for you are (from Sage's point
> of view) perfectly aware of what you are doing when you intersect :
> - The orbit of a vertex which you obtained by doing g.action( x, action =
> "OnPoints" )
> - The orbit of an edge which you obtained by doing g.action( (x,y), action
>= "OnSets")

No, this won't really fly. Indeed,
we can follow your design, and implement, explictly, action on tuples of
tuples. And then, on my example with the Z_3 action, ask for the orbit on ((1,2),(1,2)).
And then we are in trouble, cause there is no way to figure out
whether (1,2) is a domain element or not!

Dima

[Nathann Cohen]

> No, this won't really fly. Indeed,
> we can follow your design, and implement, explictly, action on tuples of
> tuples. And then, on my example with the Z_3 action, ask for the orbit on
> ((1,2),(1,2)).
> And then we are in trouble, cause there is no way to figure out
> whether (1,2) is a domain element or not!

You can decide this from the value of "action".

Nathann

[Nathann Cohen]

> Do you mean to say that we check that (1,2) is in the domain, and
> utilize this info?

O_O

Are you doing this on purpose ?

If you want to find the "orbit" of ((1,2),(1,2)) with Sage and if we implement this "action" thing, then :

- When you write g.action( ((1,2),(1,2)), action="OnPoints") Sage refuses what you give it for ((1,2),(1,2)) does not belong to the domain
- When you write g.action( ((1,2),(1,2)), action="OnTuples") then Sage checks that (1,2) is indeed in the doman (it is a vertex of your circuit) and returns [((1,2),(1,2)), (1,1), (2,2)], that is a set of pairs (vertex, vertex)
- When you write g.action( ((1,2),(1,2)), action="OnSets") Then Sage either refuses to work because your "set" contains twice the same element, or reduces your "set" to ((1,2)) in which case it returns a list of sets equal to [((1,2)), (1), (2)]

When is it ambiguous ?

Nathann

[Nathann Cohen]

If your only problem is Volker's proposition that we "guess" the value of "action" according to the input I do not mind forgetting about it just to simplify this discussion, even though I think his idea is good.

Then you would not be able to call "orbit" without specifying the value of "action", and this terminates all doubts about the interpretation of input and output.

Nathann

[Volker Braun]

Under my proposal, the orbit of ((1,2),(1,2)) would be the orbit of a pair, i.e.  {((1,2),(1,2)), (1,1), (2,2)}. If you want the orbit of pairs of pairs, you can get it as orbit(..., action="OnTuplesTuples").

There is of course a limit of how nested the action is. If you really need orbits of tuples of sets of tuples of sets of tuples then you'll have to relabel the permutation group so that its domain doesn't have tuples or sets.

[Nathann Cohen]

> There is of course a limit of how nested the action is. If you really need
> orbits of tuples of sets of tuples of sets of tuples then you'll have to
> relabel the permutation group so that its domain doesn't have tuples or
> sets.

? But Whyyyyyyyyyyyyyyyyy should we relabe anythin ??? Whenever there is a doubt as to how INPUT should be read you can feed the method with a corresponding value of 'action', and the uncertainty disappears !!!

Besides we only compute orbits by forwarding stuff to GAP. We it does not know how to do we cannot do either.

Volker, your trick is nice because it means that it is mostly useless to define the value of "action" explicitly, but if there is a doubt just define action manually and there is *NO* uncertainty possible.

Nathann

[Dima Pasechnik]

On 2013-03-22, Nathann Cohen <nathan...@gmail.com> wrote:

> --f46d040f9ba41d2f1404d88653eb
> Content-Type: text/plain; charset=ISO-8859-1

In more detail: one writes a function that can do GAP's OnTuplesTuples action,
without even any action guessing involved (this is trivial code,
right, we have things like this on our ticket?), and asks it to do the
orbit of the tuple of tuples ((1,2),(1,2)). The outcome --- the stuff is
terribly broken --- is explained in
my previous message. In particular, the "nicest" case --- infinite orbit
--- is where by ((1,2),(1,2)) the caller gets his wish, to compute the orbit on the
tuple of tuples of vertices of his graph, granted. Of course I assume
that the function cannot read the mind of the caller as it goes to work,
so it has to make a consistent choice that (1,2) is not a domain element...

Just as one can derive anything from a False statement, one can always
get into trouble with design that creates counterexamples to foundations
of group theory.

Dima

>
> Nathann
>

[Nathann Cohen]

Helloooooo !

> In more detail: one writes a function that can do GAP's OnTuplesTuples action,
> without even any action guessing involved (this is trivial code,
> right, we have things like this on our ticket?), and asks it to do the
> orbit of the tuple of tuples ((1,2),(1,2)). The outcome

The output would be [ ((1,2),(1,2)), ((2,(1,2)),(2,(1,2))), (((1,2),1),((1,2),1)) ]

What is the problem with that ? If you say OnTupleTuple you know that (1,2) has to be considered as the tuple with two elements 1,2 and we can do the job. You know this because it is an action on a tuple of tuple, the tuple of tuple being ((1,2), (1,2)). So there are two tuples, which are (1,2) and (1,2), each one containing two elments. No way you can confuse this with the element (1,2).

> Just as one can derive anything from a False statement, one can always
> get into trouble with design that creates counterexamples to foundations
> of group theory.

Tell me how it is wrong or the mistake I made. Otherwise it works.

Nathann

[Nathann Cohen]

> Even if you manage to answer the question above satisfactory,
> I still hold that it's not acceptable in the first place to have such
> design,
> forcing one to jump through hoops for no good reason, in an extendable
> system like Sage.

This design is CORRECT Dima, if you don't believe so just give me one instance for which there is an uncertainty.

OnTupleTupleTupleTupleTuple would tell you that the first 5 layers are NOT elements from the domain, and that only the elements of depth 6 are elements of the domain.

Nathann

[Nathann Cohen]

> no, the 3rd element is computed using a different meaning of (1,2) than
> the one used to compute the 2nd one.
> If you used the same meaning for the 2nd as the one for the 3rd, your
> 2nd would be (1,1).

Then how is your input of type "Tuple of Tuple", sir ?

> OK, great, so (1,2) is not an element.
> Yet, you take (1,2) as an element when you compute the 3rd element of
> the orbit. Is your implementation of the function going to read your
> mind, to work correctly?

Of course, because the type of the value returned is "A list of tuple of tuple". Hence everything at depth <= 3 is a container,and everything at depth 4 is an element.

Nathann

[Volker Braun]

We are talking about guessing the action once and for all for a given input. You are talking about guessing the action each time a group element acts in the orbit. I agree that the latter is not consistently doable. But it is possible to guess the action in the beginning of the orbit computation, and this is unambiguous.

Other points that might be nice to implement (but are not on the ticket):

* a switch to optionally print the guess used for the action, maybe verbose=True or action="guess_verbose".

* allow any python function f(g,x) as action=f

[Dima Pasechnik]

On 2013-03-23, Volker Braun <vbrau...@gmail.com> wrote:
> ------=_Part_1329_18134862.1364030357521
> Content-Type: text/plain; charset=ISO-8859-1

>
> We are talking about guessing the action once and for all for a given
> input. You are talking about guessing the action each time a group element
> acts in the orbit. I agree that the latter is not consistently doable. But
> it is possible to guess the action in the beginning of the orbit
> computation, and this is unambiguous.

Unless you specify the action explicitly,
you will need to run a syntactic parser on the group domain before you
can compute an orbit, or do any other sem-trivial computation.
Certainly part 2 of
http://trac.sagemath.org/sage_trac/ticket/14291#comment:28
will not be possible to achieve.

Say, you have 1, 2, (1,2), (2,(1,2)), and perhaps other stuff in the domain.
How many different meanings does "the orbit of ((2,(1,2)),((2,(1,2)))" have?
How can you guess the "right" action for it?

Dima
(recycling a part of another message in this thread, sorry)

[Nathann Cohen]

> Say, you have 1, 2, (1,2), (2,(1,2)), and perhaps other stuff in the domain.
> How many different meanings does "the orbit of ((2,(1,2)),((2,(1,2)))" have?
> How can you guess the "right" action for it?

Dima it's getting boring. Let's say that I do not try to guess
anything if that's a problem, do we agree that a function named
"orbit" which knows the type of its input from the value of "action"
wiill never encounter a ambiguous input nor return an ambiguous output
?

Nathann

[Volker Braun]

On Saturday, March 23, 2013 1:43:05 PM UTC+1, Dima Pasechnik wrote:

Now,  if 1, 2, and (1,2) are in your domain, is (2,(1,2)) a tuple?

According to the "minimum depth" rule to guess the default action, it is.

 

And how many different meanings does ((2,(1,2)),((2,(1,2))) have?

There is a unique guess according to the "minimum depth" rule, if that is not what you want then you have to specify the action explicitly.

[Nathann Cohen]

Helloooooooooooooooooooooooooo Dima !!!

Yesterday I went to walk  around the Calanques near the University of Marseille, and it did me good ! I am now wandering homeless in Paris and that's another story :-P

Buttttttttt the thing is that I thought a bit about our conversation here and I think I understand our misunderstanding better. That's only because Thomas Connor mad me read something about Incidence Geometry a long time ago :-D

So for a start, it took me some time to accept that you see nothing wrong -- in a group where all elements of the domain are integers 1, .... , n -- with wanting to compute the orbit of (1, {1,2}), when of course {1,2} is not a member of the domain. Of course, now if {1,2} *IS* a member of the domain then you do not see how to interpret (1, {1,2}) given as input and everything becomes dark, sad, evil and totally non-beautiful at all.

SO. First, the thing is that GAP apparently does not know how to do that either. It accepts only a list of things which are "at the same level", that is a tuple (element, element) and not a tuple (element, pair of elements). That's what I need myself so I don't complain if GAP does not know better and I would be prettyyyyyy glad if this feature could be exposed for a start. And for this kind of input we know all we have to with the value of "action" exactly as GAP already does it.

Then I agree that it would be great to have a way to say g.orbit( (1, {1,2}) ) and have Sage do all the job. Well, at this level I have no idea how it should be actualy implemented (I'm interested in the ways but so ignorant of such things that I probably will not be of much help), but I am not scared anymore of the interpretation of input : as Volker said earlier (which I had not noticed then) we could just write some code at the beginning of "orbit" which checks that input can never be misnterpreted (and cache the result of this computation) so that we can be proud of what we return. And if input can be misinterpreted we would just scream in panic and raise an IAmClueless error saying so. Which will not happen in your applications, which will not happen in mine either, and which will never happen whenever "action" is defined anyway

Now what you think of it ? That we implement this method for a given value of "action", and think hard of how to extend GAP's features in Sage ?

Have fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuun ! It's grey in Paris and everything is expensive, but I have found a couch somewhere for the next two weeks ;-)

Nathann

[tom d]

Hm, wouldn't this just be a direct product of the individual group actions?  It seems to me that we're expecting the permutations to act according to an 'obvious' group action.  Should we also expect 'obvious' actions of things like a dihedral group when given a 2-dimensional vector?  Probably the answer is to generalize and build up a proper group actions category (with obvious methods passing to representations!).

It looks like there's a bare semblance of a glimmer of the idea of actions in Sage:
http://combinat.sagemath.org/doc/reference/categories/sage/categories/action.html
but it's not very fleshed out....

One way to deal with the problem at hand would be to define a direct product of group actions and behave/coerce accordingly.  This could look something like:
1) Look at the list of things the permutation is supposed to be acting on, like [1, Set([1,2])]
2) Build a group action parent for each of the components, which we then use to build a direct product parent
3) Return the appropriate element of the direct product.

Such a framework would have the advantage of being there to deal with similar problems in other groups.

cheers!

[Jason B. Hill]

Nice catch Dima!

This functionality is nice, although I think a competent programmer in Sage/Python realizes that the object (1,2) is a bit too vague/polymorphic. It DOES have a use in at least helping explain the theory though. The following example is a small demonstration. I'm simply using text strings as cycles/tuples. I don't need to cast those as actual sets/permutations/tuples for this example, and I suppose I'd question taking the underlying code that far in general.

Example:

Consider the symmetric group $S_3$. The action that most are familiar with is the natural action of degree 3. Call that $G$. Another action is the (right) regular action of $S_3$ acting on itself. We label the six group elements with strings as follows: '()', '(1,2)', '(1,3)', '(2,3)', '(1,2,3)', '(1,3,2)'. It may be easier to think of these elements as being labeled by letters for now. We'll use

'()'=a, '(1,2)'=b, '(1,3)'=c, '(2,3)'=d, '(1,2,3)'=e, '(1,3,2)'=f

For instance, we have a*b=a and c*d=e, and one could write out the entire multiplication table as a 6x6 array. Now, in the regular action, we're looking at a group that permutes the group elements themselves ... which is a bit meta ... but it is generated by (if you don't see where I'm getting this from, you may want to draw our the multiplication table) a two-cycle and a three-cycle: (a,b)(c,f)(d,e) and (a,e,f)(b,c,d). Written in the original cycle strings, those generators are:

('()','(1,2)')('(1,3)','(1,3,2)')('(2,3)','(1,2,3)') and ('()','(1,2,3)','(1,3,2)')('(1,2)','(1,3)','(2,3)')

Coding that in Sage...

G=PermutationGroup([[('()','(1,2)'),('(1,3)','(1,3,2)'),('(2,3)','(1,2,3)')],[('()','(1,2,3)','(1,3,2)'),('(1,2)','(1,3)','(2,3)')]])
G.is_isomorphic(SymmetricGroup(3))
  True

So, we have a degree 6 representation of $S_3$. In fact, we can go further. Let's place the degree 6 regular representation in a fully diagonal subdirect product with the natural action. I'll use letters here instead of the ugly strings.

G=PermutationGroup([[('a','b'),('c','f'),('d','e'),(1,2)],[('a','e','f'),('b','c','d'),(1,2,3)]])
G.degree()
  9
G.is_isomorphic(SymmetricGroup(3))
  True


Interestingly, this subdirect product that I just formed is a small example of a permutation group having two different length minimal nonredundant bases. (The regular representation always has a single base element, while the natural representation of the symmetric group has a degree-1 minimal nonredundant base.) Try finding such a small example in the literature.

I really caution group theorists to stop thinking of permutation group elements as being things like (1,2). As tom d hinted at, that is an action. Permutation groups are better understood as abstract groups acting on a domain, and we only ever have access to the action ... and the worst part of it all is that the same abstract group can induce infinitely many different actions. $S_4$ acting in rotations on the cube is another good example of this.

Jason

--
You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-d...@googlegroups.com.
To post to this group, send email to sage-comb...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Jason B. Hill
http://www.jasonbhill.com  |  ja...@jasonbhill.com

[Volker Braun]

The group action category stuff would be nice, but you would run into exactly the same question that Dima asked: What are you going to do if there is more than one possible action. You'll have to either use some heuristics (take the simpler / less nested action) or raise some exception telling the user to explicitly disambiguate between them. 

[tom d]

Specify the action!  By making a group action framework, we would also be providing the possibility of changing the action to something contrary to the assumptions of the original developers.... Yes, in fact I think this is one of the natural reasons for doing an explicit group action framework.  Even for the action of S_n on the set {1,2,3,...,n} one can twist the 'usual' action with an automorphism \phi of S_n, so that \sigma acts on i by \phi(\sigma)(i).  

The 'usual' actions then become special predefined objects, like the special graphs, maybe summoned up automatically using the permutation/whatever's __call__ function if it's an idiomatic action like \sigma(3).

As a category, I would imagine we would have a GroupAction category and/or a GroupWithAction category, which would put some requirements on the group and its elements.

I've attached a bit of sample code, which could be used as a base to start a group action category.  (Currently just a class, as I need to go and read the category tutorials, though...)  The examples are at the bottom; includes products of actions, twisting by a group endomorphism, computing characters, orbits, checking the action definition, checking transitivity, and generating the Cayley graph of the action for a given generating set.....

[tom d]

oops, here's the code!  I keep getting server erros when trying to attach as a file, so I'm just including the text of the code file below:

class GroupAction(Parent):

    def __init__(self, G, S, phi):

        #phi a group action G\times S \rightarrow S

        self.phi=phi

        self.G=G

        self.S=S

    def __repr__(self):

        return "Action of "+self.G.__repr__()+" on the set "+self.S.__repr__()

    def action(self, g, s):

        """

        Gives the action of g on s.

        """

        return self.phi(g,s)

    def group(self):

        """

        Group which acts.

        """

        return self.G

    def gset(self):

        """

        Set on which the group acts.

        """

        return self.S

    def action_function(self):

        """

        Function from `G\times S \rightarrow S`.

        """

        return self.phi

    def check_action(self, g, h, s):

        """

        Checks whether g(hs)=(gh)s.

        """

        return self.phi(g*h,s)==self.phi(g,self.phi(h,s))

    def check_action_full(self, gens=None, contragradiant=False):

        """

        Checks that this is actually a group action using a generating set for

        the group acting on the full set.

        """

        assert self.S.is_finite(), 'Cannot check group action on an infinite set.'

        if gens==None:

            #Should check if g has gens implemented.

            gens=self.group().gens()

        for g in gens:

            for h in gens:

                for s in S:

                    if contragradiant:

                        if not self.phi(g*h,s)==self.phi(g,self.phi(h,s)):

                            stringy=g.__repr__()+', '+h.__repr__()+' '+s.__repr__()

                            assert False, 'Action fails on '+stringy

                    else:

                        if not self.phi(h*g,s)==self.phi(g,self.phi(h,s)):

                            stringy=g.__repr__()+', '+h.__repr__()+' '+s.__repr__()

                            assert False, 'Action fails on '+stringy

        return True

    def orbit(self, s):

        return Set([self.action(g,s) for g in self.group()])

    def is_transitive(self):

        if len(self.gset())==0: return True

        s=self.gset()[0]

        return orbit(s)==Set(self.gset())

    def twist(self, endomorphism):

        """

        Twists this representation by an endomorphism of the group.

        """

        phi=self.action_function()

        kappa=lambda g,s: phi( endomorphism(g), s)

        return GroupAction(self.G, self.S, kappa)

    def character(self):

        """

        Count fixed points for conjugacy class representatives.

        """

        c=[]

        for g in self.G.conjugacy_classes_representatives():

            fix=0

            for s in self.S:

                if self.action(g,s)==s: fix+=1

            c.append(fix)

        return c

    def cayley_graph(self, gens=None):

        """

        Builds a cayley graph of the group action, using the specified generating set.

        """

        assert self.S.is_finite(), 'Cannot check group action on an infinite set.'

        if gens==None:

            #Should check if g has gens implemented.

            gens=self.group().gens()

        G=DiGraph()

        for g in gens:

            for s in self.gset():

                G.add_edge( s, self.action(g,s) )

        return G

    def product_action(self, B):

        """

        Given a second group action B with the same group and set T, generates

        the product group action of self and B.

        """

        assert self.group()==B.group(), 'Actions need to have same group acting.'

        T=B.gset()

        U=CartesianProduct(self.gset(),T)

        kappa=lambda g, u: U( [self.action_function()(g,u[0]), B.action(g,u[1])] )

        return GroupAction(G,U,kappa)

"""

#Example 1: Usual symmetric group action.

sage: G=SymmetricGroup(4)

sage: S=Set([1,2,3,4])

sage: phi = lambda g,s: g(s)

sage: A=GroupAction(G,S,phi)

sage: A.character()

[4, 2, 0, 1, 0]

#Example 2: Symmetric group acting on a set.

sage: rho=lambda g,s: Set([phi(g,t) for t in s])

sage: T=Subsets(S,2)

sage: B=GroupAction(G,T,rho)

sage: B.character()

[6, 2, 2, 0, 0]

#Example 3: Product action.

sage: C=A.product_action(B)

sage: C.character()            

[24, 4, 0, 0, 0]

#Example 4: Twist by an automorphism.

sage: a=G.an_element()^2

sage: ai=a.inverse()

sage: auto=lambda g: a*g*ai

sage: At=A.twist(auto)

sage: y=G.simple_reflection(1)

sage: [A.action(y,s) for s in S]

[2, 1, 3, 4]

sage: [At.action(y,s) for s in S]

[1, 2, 4, 3]

"""

[Benjamin Jones]

Big +1 to framework for explicitly instantiating group actions.

--
Benjamin Jones
benjami...@gmail.com

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[Nathann Cohen]

> As a category, I would imagine we would have a GroupAction category and/or
> a GroupWithAction category, which would put some requirements on the group
> and its elements.

I hate categories T_T

Categories is where everything I cherish gets ruined T_T

Nathann

[Nathann Cohen]

Helloooooooooooooooooooooo !!!

> Well, unfortunately I don't know under which Seine bridge mathematicians
> are most
> welcome :-)

Ahahahah. I felt so shocked when I first learnt that Paris did not have the only one O_O

> Mind you, when this part of GAP was developed, you were in primary
> school;-),

And I had more important things to do, like looking for sweets. I will not be held responsible.

> computers were slow and weak, everything needed to be coded
> in C or Fortran (or one would need to use Lisp, which wasn't very
> popular in that part of computational algebra --- unfortunately);
> naturally, some features remain hugely underdeveloped due to this. IMHO
> a part of the GAP framework of actions which deals with tuples, subsets,
> etc.
> is at present more of a burden than of an advantage. (Whereas actions
> say on cosets of a subgroup which GAP has are hugely important and hard to
> beat)

Hmmm... But then, should we patch Sage to add features or patch GAP and use it in Sage ? :-P

> Coding more generic orbit algorithms for permutation groups
> in a language like Python is, moreover, quite easy.
> (By more generic---than tuples, tuples of tuples, etc---
> I mean the action on trees with leafs labeled by
> elements of the group domain, and with some (fixed) non-terminal node
> might
> carry out the structure of a set, i.e. have unordered rathen than
> ordered neighbourhoods. E.g. you can get an action on gadgets like
> (1,{2,3},((4,5),2,{1,6,7})); here the domain elements are numbers, but
> this need not be a restriction.)
> Just get yourself a queue, put there the starting element, and add the
> new images to the other end of the queue, while computing the images of
> the 1st in order element in the queue.
> One is done when everything in the queue is processed

Yep yep. In my world that's called a depth-first-search. But we are shy guys, especially when surrounded by real mathematicians.

> All the orbit algorithm needs to know, apart from the group generators,
> is how to compute the image is the tree "shape", i.e. no labels on the
> nodes.
> E.g. for the example above the shape is encoded by
> (,{,},((,),,{,,})).
>
> And this can be made modular etc, as there are more actions around than
> these which fit this pattern; so how to compute the action can be
> specified by a function passed as a parameter. (Not sure if one also
> needs a function to compare orbit elements for equality.)

Oh. You'd give "(,{,},((,),,{,,}))" as a string parameter, parse it and use it to define the tree ? Ahahaha. Funny and efficient ! A bit .... "home-made", but I like that :-P

Actually, what would have prevented me from dirtying beautiful groups with my out-of-place graph approach (i.e. the DFS above) is that I would have thought the group guys were too smart to use such things. Is that how GAP computes orbits ? Just a BFS ? A "set" object, hash functions for the group's elements, and that's all we need for a "state of the art" orbit method ?

> I wrote above how I'd see this done.
> I think it's better to encode the "usual" types of action by such a
> pattern like above (e.g. (,{,},((,),,{,,}))).
> Such a pattern can either be guessed/computed by Volker's rules, or
> specified as a parameter. (And a user function  to compute the action
> can also be a parameter).
> They could be translated into GAP actions and GAP calls, for which such
> actions exist.

Ok good point. But now I have a more pratical question : can we get #14291 after just replacing this "action" parameter with your funny string, and return a "notimplementederror" when the value of action cannot be forwarded to GAP ?
As it is, it is already a nice feature for humble graph theoreticians to compute the orbit of a pair of elements :-)

Nathann

[Dima Pasechnik]

On 2013-03-26, Nathann Cohen <nathan...@gmail.com> wrote:
> --bcaec54315d24dec2004d8cfa610
> Content-Type: text/plain; charset=ISO-8859-1

no, DFS uses a stack, i.e. LIFO (Last In First Out), not a queue (FIFO, First
in First Out), isn't it?

>
>> All the orbit algorithm needs to know, apart from the group generators,
>> is how to compute the image is the tree "shape", i.e. no labels on the
>> nodes.
>> E.g. for the example above the shape is encoded by
>> (,{,},((,),,{,,})).
>>
>> And this can be made modular etc, as there are more actions around than
>> these which fit this pattern; so how to compute the action can be
>> specified by a function passed as a parameter. (Not sure if one also
>> needs a function to compare orbit elements for equality.)
>
> Oh. You'd give "(,{,},((,),,{,,}))" as a string parameter, parse it and use
> it to define the tree ? Ahahaha. Funny and efficient ! A bit ....
> "home-made", but I like that :-P
>
> Actually, what would have prevented me from dirtying beautiful groups with
> my out-of-place graph approach (i.e. the DFS above) is that I would have
> thought the group guys were too smart to use such things. Is that how GAP
> computes orbits ? Just a BFS ? A "set" object, hash functions for the
> group's elements, and that's all we need for a "state of the art" orbit
> method ?

and a queue. A bit of discipline never hurts :)
Otherwise, that's all is needed. But indeed, it's not totally obvious.
I know very smart people, much smarter
than me, who instead computed orbits by listing all the elements of the
group first, and applying them all...

>
>> I wrote above how I'd see this done.
>> I think it's better to encode the "usual" types of action by such a
>> pattern like above (e.g. (,{,},((,),,{,,}))).
>> Such a pattern can either be guessed/computed by Volker's rules, or
>> specified as a parameter. (And a user function to compute the action
>> can also be a parameter).
>> They could be translated into GAP actions and GAP calls, for which such
>> actions exist.
>
> Ok good point. But now I have a more pratical question : can we get #14291
> after just replacing this "action" parameter with your funny string, and
> return a "notimplementederror" when the value of action cannot be forwarded
> to GAP ?
> As it is, it is already a nice feature for humble graph theoreticians to
> compute the orbit of a pair of elements :-)

I guess this should work, but I have negative amount of time available
in the coming two weeks...

Dima

>
> Nathann
>

[Volker Braun]

On Tuesday, March 26, 2013 7:01:40 AM UTC+1, tom d wrote:

Specify the action!  [...] The 'usual' actions then become special predefined objects, like the special graphs, maybe summoned up automatically using the permutation/whatever's __call__ function if it's an idiomatic action like \sigma(3).

The group action framework is just the implementation, you still haven't answered the question that this thread was about: Should permutation actions on nested containers automatically discover one possible action or not. As you said, in the group action framework you can implement either possibility. You can also implement either if you don't use it. 

In any case, http://trac.sagemath.org/14291 is about hooking up GAP and not creating a framework for group actions. So in the interest of a finite amout of work per ticket, we should probably fall back to only allow explicitly specified group actions (OnPoints/OnTuples etc) there. Once your group action framework is in place it'll be easy enough to hook that up into the orbit method as well.

[Martin]

Implementing the idea of a GroupAction category would be also of great
help for the species framework!  I could then finally properly
implement the remaining constructions, where (if I remember correctly)
I need to specify actions of a Young subgroup on a set.  In particular
this concerns unlabelled enumeration of composition.  Although one can
do without (as in the original Aldor code), it's ugly.

Best,

Martin

[Nathann Cohen]

Yoooooooooooooooo !!!

> no, DFS uses a stack, i.e. LIFO (Last In First Out), not a queue (FIFO, First
> in First Out), isn't it?

Indeed. Both would work in this case, though :-P

> and a queue. A bit of discipline never hurts :)
> Otherwise, that's all is needed. But indeed, it's not totally obvious.
> I know very smart people, much smarter
> than me, who instead computed orbits by listing all the elements of the
> group first, and applying them all...

They were just above things like runtime.

> I guess this should work, but I have negative amount of time available
> in the coming two weeks...

Well, then in the meantime I uploaded a new patch to #14291 that can be reviewed right now :-P

It implements a orbit() method only, that deals with the many actions you wanted to have available, as well as with the two I needed myself. It even sorts the "Set" stuff before feeding GAP with it, which will avoid a few raised eyebrows when GAP does not like what it is given (especially when the user has no way to guess GAP's ordering of the elements !).

Waiting for a review ! :-)

Nathann

[Nicolas M. Thiery]

For whatever it's worth, there is some preliminary stuff in this
direction in the queue:

http://combinat.sagemath.org/code/file/tip/sage/categories/sets_with_action.py

It's more geared toward sets endowed with an action of a semigroup,
but the category part should scale to groups.

There is also some support for defining actions in
sage.categories.action.py; of course the two things should be made to
work hand in hand. This seems like a good thing to discuss at Sage
Days in June!

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

[Benjamin Jones]

On Tue, Mar 26, 2013 at 3:34 AM, Volker Braun <vbrau...@gmail.com> wrote:

In any case, http://trac.sagemath.org/14291 is about hooking up GAP and not creating a framework for group actions. So in the interest of a finite amout of work per ticket, we should probably fall back to only allow explicitly specified group actions (OnPoints/OnTuples etc) there. Once your group action framework is in place it'll be easy enough to hook that up into the orbit method as well.

+1 

[tom d]

'Allo!

On Tuesday, March 26, 2013 1:34:32 PM UTC+3, Volker Braun wrote:

The group action framework is just the implementation, you still haven't answered the question that this thread was about: Should permutation actions on nested containers automatically discover one possible action or not. As you said, in the group action framework you can implement either possibility. You can also implement either if you don't use it. 

Yeah, I was thinking that because of the ambiguity that was being discussed in dealing with the nested actions, the best approach would be to provide a simple framework for specifying actions, and easy-to-access examples of That Sort of Thing, for people interested in using it, rather than putting in an implementation which half of users will think is mussed up.

I'll be at the Sage-Combinat days in June; helping to build out the action code that others have already started developing sounds like a great way to spend at least a chunk of that week.

[Nathann Cohen]

Hellooooooooooooooo !!

> Yeah, I was thinking that because of the ambiguity that was being discussed in dealing with the nested actions, the best approach would be to provide a simple framework for specifying actions, and easy-to-access examples of That Sort of Thing, for people interested in using it, rather than putting in an implementation which half of users will think is mussed up.
>
> I'll be at the Sage-Combinat days in June; helping to build out the action code that others have already started developing sounds like a great way to spend at least a chunk of that week.

Ahaahahhah. I would be very surprised (and glad. but very surprised.) if you had a way to beat Dima's every efficient encoding of the action with a string ! :-)

Have fuuuuuuuuuuuuuuuuuuun !

Nathann

[Nils Bruin]

On Mar 26, 10:04 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:

> It's more geared toward sets endowed with an action of a semigroup,
> but the category part should scale to groups.

+1. I'm pretty sure that whatever the user interface is going to be,
something along these lines will have to go underneath to build a
solid basis. If you like to pander to the number theoretic crowd, you
could call the category "GSet" and, the case where the acted-upon-set
is a commutative group itself, "GModule".

[Nathann Cohen]

Helloooooooooooooooo !!!

> No, I didn't propose strings. I meant things like
>
> sage: (None,None,{None,None},None)
> (None, None, set([None]), None)
>
> Now you can replace None with elements of the group domain.

Oh ? Then I still don't get it. I thought that you meant that the input should be something like :

g.orbit(weird_mix_of_tuples_sets_and_elements, action = (, ,)) so that the value of "action" says where elements should be.

And I thought that it would be a string, because you can't do things like that :

{1, 1}

(which may happen when this function is called by other ones which do not know what the parameters are

And more importantly you can't do that :

{{}}

So I thought you said that something like g.action((1,(1,2)), action = "(,)") could mean g.action((1,(1,2)), action = "OnPairs")

Nathann