provide a framework for finite group actions

[mantepse]

This ticket provides an easy user interface to define a permutation group corresponding to a finite group action.

sage: a = lambda x: (2*x) % 7
sage: H = PermutationGroup(action=a, domain=range(7))
sage: H.orbits()
[[0], [1, 2, 4], [3, 6, 5]]
sage: H.gens()
[(1,2,4), (3,6,5)]

sage: a = lambda g, x: vector(g*x, immutable=True)
sage: X = [vector(x, immutable=True) for x in GF(3)^2]
sage: G = SL(2,3); G.gens()
(
[1 1]  [0 1]
[0 1], [2 0]
)
sage: H = PermutationGroup(G.gens(), action=a, domain=X)
sage: H.orbits()
[[(0, 0)], [(1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]]
sage: H.gens()
[((0,1),(1,1),(2,1))((0,2),(2,2),(1,2)),
 ((1,0),(0,2),(2,0),(0,1))((1,1),(1,2),(2,2),(2,1))]

Depends on #33824

CC: @tscrim @kcrisman

Component: group theory

Author: Martin Rubey

Branch/Commit: fdea936

Reviewer: David Joyner, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/33784

[mantepse]

Branch: u/mantepse/provide_a_framework_for_finite_group_actions

[mantepse]

Commit: b77e8ce

[mantepse]

Author: Martin Rubey

[mantepse]

comment:2

Sage should have an easy to use and efficient framework to play with finite group actions.

---

New commits:

b77e8ce

initial idea

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

15d1c15

design action as subclass of PermutationGroup_generic

[sagetrac-git]

Changed commit from b77e8ce to 15d1c15

[sagetrac-git]

Changed commit from 15d1c15 to 067bc8b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

067bc8b

remove initial idea

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

00f5169

add doctests

[sagetrac-git]

Changed commit from 067bc8b to 00f5169

[mantepse]

comment:8

This ticket provides an easy user interface to define a permutation group corresponding to a finite group actions.

        sage: a = lambda x: (2*x) % 6                                                                                                                                                        
        sage: X = [0,1,2,3,4,5]                                                                                                                                                              
        sage: G = PermutationGroup(action=a, domain=X)                                                                                                                                       
        sage: G.orbits()                                                                                                                                                                     
        [[0], [1, 2, 4], [3], [5]]                                                                                                                                                           
                                                                                                                                                                                             
        sage: a = lambda g, x: vector(g*x, immutable=True)                                                                                                                                   
        sage: X = [vector(x, immutable=True) for x in GF(3)^2]                                                                                                                               
        sage: G = SL(2,3); G.gens()                                                                                                                                                          
        (                                                                                                                                                                                    
        [1 1]  [0 1]                                                                                                                                                                         
        [0 1], [2 0]                                                                                                                                                                         
        )                                                                                                                                                                                    
        sage: H = PermutationGroup(G.gens(), action=a, domain=X)                                                                                                                             
        sage: H.orbits()                                                                                                                                                                     
        [[(0, 0)], [(1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]]                                                                                                         
        sage: H.gens()                                                                                                                                                                       
        [((0,1),(1,1),(2,1))((0,2),(2,2),(1,2)),                                                                                                                                             
         ((1,0),(0,2),(2,0),(0,1))((1,1),(1,2),(2,2),(2,1))]    

[kcrisman]

comment:10

This is nice. Some questions.

This ticket provides an easy user interface to define a permutation group corresponding to a finite group actions.

        sage: a = lambda x: (2*x) % 6                                                                                                                                                        
        sage: X = [0,1,2,3,4,5]                                                                                                                                                              
        sage: G = PermutationGroup(action=a, domain=X)                                                                                                                                       
        sage: G.orbits()                                                                                                                                                                     
        [[0], [1, 2, 4], [3], [5]]                                                                                                                                                           
                     

Is there any checking that this is meaningful, or is it garbage in, garbage out? Such as if one changed the lambda function here to be modulo 5, or 100. (I know that 100 is garbage, I think 5 would be as well.)

Also, should it print out differently? You do PermutationGroup_generic.__init__ and presumably this defines its string representation.

Can we do group operations (I mean like semi/direct product etc.) on it with others? Does each (finite permutation) group automatically have an extension to this with a natural action (and would that be conjugation, right mult., left mult.)? I'm just a little concerned about how it might be able to integrate in long-term with other group stuff.

[mantepse]

comment:11

Replying to @kcrisman:

This is nice.

Thank you :-)

        sage: a = lambda x: (2*x) % 6                                                                                                                                                        
        sage: X = [0,1,2,3,4,5]                                                                                                                                                              
        sage: G = PermutationGroup(action=a, domain=X)                                                                                                                                       
        sage: G.orbits()                                                                                                                                                                     
        [[0], [1, 2, 4], [3], [5]]                                                                                                                                                           
                     

Is there any checking that this is meaningful, or is it garbage in, garbage out? Such as if one changed the lambda function here to be modulo 5, or 100. (I know that 100 is garbage, I think 5 would be as well.)

Currently it is garbage in, garbage out. Do you have any checks in mind one could do?

Maybe it would even be possible to allow domain being specified only partially. That is, it should suffice to include one element per orbit, to generate the full domain.

Also, should it print out differently? You do PermutationGroup_generic.__init__ and presumably this defines its string representation.

Since PermutationGroup(action=a, domain=X) is just yet another way to define a PermutationGroup, it should be a PermutationGroup and print as such. Note that only the image of 𝐺 → 𝔖_𝑋 is remembered. (Can't trac do LaTeX?)

Can we do group operations (I mean like semi/direct product etc.) on it with others? Does each (finite permutation) group automatically have an extension to this with a natural action (and would that be conjugation, right mult., left mult.)? I'm just a little concerned about how it might be able to integrate in long-term with other group stuff.

Does my reply above answer this question?

[mantepse]

comment:12

Replying to @mantepse:

Replying to @kcrisman:

        sage: a = lambda x: (2*x) % 6                                                                                                                                                        
        sage: X = [0,1,2,3,4,5]                                                                                                                                                              
        sage: G = PermutationGroup(action=a, domain=X)                                                                                                                                       
        sage: G.orbits()                                                                                                                                                                     
        [[0], [1, 2, 4], [3], [5]]                                                                                                                                                           
                     

Is there any checking that this is meaningful, or is it garbage in, garbage out? Such as if one changed the lambda function here to be modulo 5, or 100. (I know that 100 is garbage, I think 5 would be as well.)

Currently it is garbage in, garbage out. Do you have any checks in mind one could do?

Actually, the map a = lambda x: (2*x) % 6 is garbage - it is not invertible and therefore certainly not the generator of a cyclic group. It should be a = lambda x: (2*x) % 5.

Currently, sage.combinat.cyclic_sieving_phenomenon.orbit_decomposition is defined as follows:

def orbit_decomposition(L, cyc_act) -> list[list]:
    orbits = []
    L_prime = set(L)
    while L_prime:
        obj = L_prime.pop()
        orbit = [obj]
        obj = cyc_act(obj)
        while obj in L_prime:
            orbit.append(obj)
            L_prime.remove(obj)
            obj = cyc_act(obj)
        orbits.append(orbit)
    return orbits

I think it would be better to make it

def orbit_decomposition(L, cyc_act) -> list[list]:
    orbits = []
    L_prime = set(L)
    while L_prime:
        fst = L_prime.pop()
        orbit = [fst]
        obj = cyc_act(fst)
        while obj != fst:
            orbit.append(obj)
            L_prime.discard(obj)
            obj = cyc_act(obj)
        orbits.append(orbit)
    return orbits

Doing so one would have to provide only one element from each orbit, and the remaining elements would be generated by the action. This might be practical sometimes. Moreover and more importantly, silly mistakes as the one above would be detected, because orbit_decomposition would go into an infinite loop.

However, we cannot have a similar behaviour for PermutationGroup(gens, domain=domain), because of the following weirdness:

sage: PermutationGroup([("a","c")]).domain()
{'a', 'c'}
sage: PermutationGroup([(1,3)]).domain()
{1, 2, 3}

So the only way to get a permutation group with domain {1, 3} is

sage: PermutationGroup([(1,3)], domain=[1,3]).domain()
{1, 3}

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8eaaba1

fix wrong doctest, improve doc

[sagetrac-git]

Changed commit from 00f5169 to 8eaaba1

[kcrisman]

comment:14

Currently it is garbage in, garbage out. Do you have any checks in mind one could do?

No, I'm not sure, but I know that Sage tends to lean in that direction. Maybe something one could ask on the list about, or David might have ideas. Glad you saw there was a mistake, by the way - I don't know why I got confused there either. Although should the empty permutation be a generator, strictly speaking?

+        sage: H.gens()
+        [(), (1,2,4), (3,6,5)]

I admit I'm a little confused about the difference between the "acting group" and the homomorphic image here.

Since PermutationGroup(action=a, domain=X) is just yet another way to define a PermutationGroup, it should be a PermutationGroup and print as such. Note that only the image of 𝐺 → 𝔖_𝑋 is remembered. (Can't trac do LaTeX?)

Hmm, so really it just a wrapper of sorts making it easier to define permutation (sub)groups on arbitrary finite sets

Can we do group operations (I mean like semi/direct product etc.) on it with others? Does each (finite permutation) group automatically have an extension to this with a natural action (and would that be conjugation, right mult., left mult.)? I'm just a little concerned about how it might be able to integrate in long-term with other group stuff.

Does my reply above answer this question?

So I guess not any differently from before.

I think it would be better to make it

Probably that could be a separate ticket, since it would be improving already-existing functionality.

sage: PermutationGroup([(1,3)]).domain()
{1, 2, 3}

Yeah, this is annoying, I've run into it before.

[mantepse]

comment:15

Replying to @kcrisman:

Although should the empty permutation be a generator, strictly speaking?

+        sage: H.gens()
+        [(), (1,2,4), (3,6,5)]

Well, PermutationGroup allows it, but I could also (manually) remove singleton orbits.

I admit I'm a little confused about the difference between the "acting group" and the homomorphic image here.

For example, the symmetric group acts on the singleton set trivially:

sage: PermutationGroup(SymmetricGroup(3).gens(), action=lambda g, x: x, domain=[1])
Permutation Group with generators [(), ()]

and there is no way to recover the symmetric group from that. I think that is okay, because any computation you want to do with the action you can actually do with the permutation group.

Hmm, so really it just a wrapper of sorts making it easier to define permutation (sub)groups on arbitrary finite sets

Indeed.

Can we do group operations (I mean like semi/direct product etc.) on it with others?

My plan is to provide a new implementation of combinatorial species, which will make computations with group actions of the symmetric group (and possibly some others) very convenient. It seems that there is very little support currently.

Does each (finite permutation) group automatically have an extension to this with a natural action (and would that be conjugation, right mult., left mult.)? I'm just a little concerned about how it might be able to integrate in long-term with other group stuff.

I am not sure what "to this" is pointing to. With my current implementation, the action of the group is not part of the data of the PermutationGroup, and I think that this is how it should be. If there is something we want to do with the action, we would indeed need a separate FiniteGroupAction class. However, currently I cannot think of anything that would justify it.

[kcrisman]

comment:16

I am not sure what "to this" is pointing to. With my current implementation, the action of the group is not part of the data of the PermutationGroup, and I think that this is how it should be. If there is something we want to do with the action, we would indeed need a separate FiniteGroupAction class. However, currently I cannot think of anything that would justify it.

Okay, this paragraph clarifies greatly what you are trying to do here. It is a little outside of my full expertise so I won't do further review, but I think this is a good start at some of your goals, and certainly for making it much easier to do permutation groups that are "non-standard".

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d088d1d

remove trivial generators

[sagetrac-git]

Changed commit from 8eaaba1 to d088d1d

[wdjoyner]

comment:23

If that's the only part needing review, then it looks good to me!

[mantepse]

comment:24

If so, please click on "modify ticket", enter your name into the "Reviewers" field and select "positive review".

Thank you so much!

[wdjoyner]

Reviewer: wdj

[wdjoyner]

comment:26

Replying to @mantepse:

If so, please click on "modify ticket", enter your name into the "Reviewers" field and select "positive review".

Thank you so much!

Done.

[tscrim]

comment:27

A few little things:

• orbits() should not return a mutable object since it is the cached object. The cached result is better as a tuple of tuples IMO. Otherwise orbits() needs to make a deep copy.
• Returns -> Return in orbits().
• Real name for the reviewer.
• It might be good to be explicit and say this is a left action.

Perhaps not such a little thing, and while it isn't necessary for a positive review, it might be good to do now:

I believe a more efficient way to compute the action for a non-cyclic group is to directly manipulate the orbits constructed for one generator rather than building the orbits for all generators and splicing them together. This requires less memory and should at most use the same number of operations. As a bit of an extreme case, take a large product of copies of the trivial group (or Z/2Z) acting on a large set.

[tscrim]

Changed reviewer from wdj to wdj, Travis Scrimshaw

[mantepse]

comment:28

Thank you Travis for joining, I was hoping for you!

Replying to @tscrim:

• orbits() should not return a mutable object since it is the cached object. The cached result is better as a tuple of tuples IMO. Otherwise orbits() needs to make a deep copy.

I noticed this too. The problem I had is that PermutationGroup_generic.orbits has the the same problem:

sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
sage: O = G.orbits(); O
[[1, 3, 4], [2]]
sage: O[0] = 1
sage: G.orbits()
[1, [2]]

I think it is important that the two methods do the same thing. Because of your next item,

• Returns -> Return in orbits().

I decided to open a new ticket to change the behaviour of PermutationGroup_generic.orbits first, and fix the "Returns".

• It might be good to be explicit and say this is a left action.

Done (in the INPUT section).

Perhaps not such a little thing, and while it isn't necessary for a positive review, it might be good to do now:

I believe a more efficient way to compute the action for a non-cyclic group is to directly manipulate the orbits constructed for one generator rather than building the orbits for all generators and splicing them together. This requires less memory and should at most use the same number of operations. As a bit of an extreme case, take a large product of copies of the trivial group (or Z/2Z) acting on a large set.

I'll think about this, but I'll first open the other ticket.

[mantepse]

Dependencies: #33824

[kcrisman]

Changed reviewer from wdj, Travis Scrimshaw to David Joyner, Travis Scrimshaw

[mantepse]

comment:31

Replying to @mantepse:

I believe a more efficient way to compute the action for a non-cyclic group is to directly manipulate the orbits constructed for one generator rather than building the orbits for all generators and splicing them together. This requires less memory and should at most use the same number of operations. As a bit of an extreme case, take a large product of copies of the trivial group (or Z/2Z) acting on a large set.

I now realise that it is unclear to me what you have in mind. Let's say that G is generated by g and h. We compute g_orbit = orbit_decomposition(domain, lambda x: action(g, x)). I also need the generators corresponding to the homomorphic image of h, which is orbit_decomposition(domain, lambda x: action(h, x)), I don't see how I could avoid that. I could apply h*g^-1 to each element in g_orbit, but I don't see how this would avoid computations.

Help appreciated!

[tscrim]

comment:32

Replying to @mantepse:

Replying to @mantepse:

I believe a more efficient way to compute the action for a non-cyclic group is to directly manipulate the orbits constructed for one generator rather than building the orbits for all generators and splicing them together. This requires less memory and should at most use the same number of operations. As a bit of an extreme case, take a large product of copies of the trivial group (or Z/2Z) acting on a large set.

I now realise that it is unclear to me what you have in mind. Let's say that G is generated by g and h. We compute g_orbit = orbit_decomposition(domain, lambda x: action(g, x)). I also need the generators corresponding to the homomorphic image of h, which is orbit_decomposition(domain, lambda x: action(h, x)), I don't see how I could avoid that. I could apply h*g^-1 to each element in g_orbit, but I don't see how this would avoid computations.

You compute orbit_decomposition() for g, and then you just apply h to each element in each orbit. If it goes to a different orbit, then you merge the two. You can stop early once you have one orbit too. I don’t think there is a way to shortcut acting on each element by each generator (at least without knowing some structure of the group). However, you do not need to hold all of the orbits for each element (i.e., also for h in your example) simultaneously. I don’t see why you also need to apply g^-1.

[sagetrac-git]

Changed commit from d088d1d to fdea936

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3f65072	make PermutationGroup_generic.orbits return a tuple of tuples, for immutability
b2a29ac	Merge branch 'u/mantepse/make_orbits_of_permutationgroup_immutable' of trac.sagemath.org:sage into t/33784/provide_a_framework_for_finite_group_actions
da2c2e5	make PermutationGroup_generic.gens return a tuple, to ensure immutability
d5adcb0	replace $...$ with `...`
90005e7	remove unused import
d8dc2e1	Merge branch 'u/mantepse/make_orbits_of_permutationgroup_immutable' of trac.sagemath.org:sage into t/33784/provide_a_framework_for_finite_group_actions
fdea936	fix doctests

[mantepse]

comment:34

Replying to @tscrim:

Thank you for explaining!

You compute orbit_decomposition() for g, and then you just apply h to each element in each orbit. If it goes to a different orbit, then you merge the two. You can stop early once you have one orbit too. I don’t think there is a way to shortcut acting on each element by each generator (at least without knowing some structure of the group). However, you do not need to hold all of the orbits for each element (i.e., also for h in your example) simultaneously. I don’t see why you also need to apply g^-1.

I still don't get it (and I made a mistake myself). Suppose the generator corresponding to g is

(x1, g x1, g^2 x1, ...) (x2, g x2, g^2 x2, ...)...

Then applying h to each element of the first orbit I obtain

(h x1, h g x1, h g^2 x1, ...)

but this is not a cycle of a generator of the homomorphic image, is it?

[tscrim]

comment:35

Ah, I think I have misunderstood what you mean by orbits. I was thinking of G-orbits for the whole group, but to define the permutation group, you need the orbits of each generator. Thus, you need to hold all of this information, which is more than you need for the G-orbits.

[mantepse]

comment:36

Indeed. In principle I only need the generators, but I think it makes sense to compute the orbits of the group action, right away instead of asking gap to do it.

For cyclic actions, the orbits are what I'm after, in fact.

[tscrim]

comment:37

Thank you. Then back to a positive review.

[vbraun]

Changed branch from u/mantepse/provide_a_framework_for_finite_group_actions to fdea936