127 views

Skip to first unread message

Mar 21, 2013, 10:10:38 AM3/21/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

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

Mar 21, 2013, 12:05:12 PM3/21/13

to sage-...@googlegroups.com

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.

Mar 21, 2013, 1:21:40 PM3/21/13

to sage-devel

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
> It seems to me that the ambiguity arises from the original statement,

"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.

Mar 21, 2013, 6:12:30 PM3/21/13

to sage-...@googlegroups.com

On 2013-03-21, Benjamin Jones <benjami...@gmail.com> wrote:

> --f46d0444e849ed15b904d871801a

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

cases it's an orbit on subsets. The trouble is that it's not

well-defined for a domain like this.

> --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
> 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.

cases it's an orbit on subsets. The trouble is that it's not

well-defined for a domain like this.

Mar 21, 2013, 11:48:00 PM3/21/13

to sage-...@googlegroups.com

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.
> 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.

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.

Cayley's lack of proper coersions/conversions drove me insane all the time.

Dima

Mar 22, 2013, 9:43:18 AM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

Mar 22, 2013, 9:51:05 AM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

> 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

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

Mar 22, 2013, 9:52:38 AM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

Nathann

Mar 22, 2013, 10:04:06 AM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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').

Mar 22, 2013, 10:06:17 AM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> For non-interactive you either perform argument validation yourself or use

> the optional parameter G.orbit(foo, action='OnTuples').

Oh. Ok, this is fine !> the optional parameter G.orbit(foo, action='OnTuples').

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

Mar 22, 2013, 10:46:39 AM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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

> 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

Mar 22, 2013, 11:25:21 AM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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".

> 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

Mar 22, 2013, 12:19:00 PM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

> --bcaec52e66033a8d1704d88510dc

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

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

> --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,
>> 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")

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

Mar 22, 2013, 12:23:09 PM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

> 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".
> 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!

Nathann

Mar 22, 2013, 12:55:38 PM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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

> 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

Mar 22, 2013, 12:58:15 PM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

Mar 22, 2013, 1:55:02 PM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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.

Mar 22, 2013, 1:58:35 PM3/22/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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 !!!> 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.

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

Mar 22, 2013, 8:02:58 PM3/22/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

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

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

>

Mar 23, 2013, 4:36:41 AM3/23/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

> 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

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.

Nathann

Mar 23, 2013, 4:39:22 AM3/23/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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

> 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

Mar 23, 2013, 5:01:39 AM3/23/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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

> 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

Mar 23, 2013, 5:19:17 AM3/23/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

Mar 23, 2013, 8:49:09 AM3/23/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

On 2013-03-23, Volker Braun <vbrau...@gmail.com> wrote:

> ------=_Part_1329_18134862.1364030357521

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

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)

> ------=_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,
> 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.

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)

Mar 23, 2013, 8:50:43 AM3/23/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

> 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
> How many different meanings does "the orbit of ((2,(1,2)),((2,(1,2)))" have?

> How can you guess the "right" action for it?

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

Mar 23, 2013, 9:26:00 AM3/23/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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.

Mar 24, 2013, 6:11:07 AM3/24/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

Mar 25, 2013, 3:33:57 AM3/25/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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!

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!

Mar 25, 2013, 4:43:19 AM3/25/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

Mar 25, 2013, 7:30:57 AM3/25/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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.

Mar 26, 2013, 2:01:40 AM3/26/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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.....

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.....

Mar 26, 2013, 2:04:45 AM3/26/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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]

"""

Mar 26, 2013, 2:49:49 AM3/26/13

to sage-...@googlegroups.com

Big +1 to framework for explicitly instantiating group actions.

--

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.

Mar 26, 2013, 3:33:11 AM3/26/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

> 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> a GroupWithAction category, which would put some requirements on the group

> and its elements.

Categories is where everything I cherish gets ruined T_T

Nathann

Mar 26, 2013, 4:24:26 AM3/26/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

> 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

Mar 26, 2013, 6:04:38 AM3/26/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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?

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

>

> --bcaec54315d24dec2004d8cfa610

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

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 :)
>> 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 ?

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 :-)

in the coming two weeks...

Dima

>

> Nathann

>

Mar 26, 2013, 6:34:32 AM3/26/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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.

Mar 26, 2013, 8:32:22 AM3/26/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

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

Mar 26, 2013, 10:47:06 AM3/26/13

to sage-...@googlegroups.com, sage-comb...@googlegroups.com

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

> no, DFS uses a stack, i.e. LIFO (Last In First Out), not a queue (FIFO, First

> in First Out), isn't it?

> 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 guess this should work, but I have negative amount of time available

> in the coming two weeks...

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

Mar 26, 2013, 1:04:51 PM3/26/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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/

Mar 26, 2013, 1:25:42 PM3/26/13

to sage-...@googlegroups.com

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

Mar 27, 2013, 11:49:45 AM3/27/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

'Allo!

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

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.

Mar 27, 2013, 3:58:49 PM3/27/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

> 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.

Have fuuuuuuuuuuuuuuuuuuun !

Nathann

Mar 27, 2013, 7:49:11 PM3/27/13

to sage-devel

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

wrote:

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".

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,
> but the category part should scale to groups.

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".

Mar 28, 2013, 3:33:37 AM3/28/13

to sage-comb...@googlegroups.com, sage-...@googlegroups.com

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

> 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

Reply all

Reply to author

Forward

0 new messages