orbit decompositions

[Martin R]

I am very frequently using the function

Signature:      orbit_decomposition(L, cyc_act) -> 'list[list]'
Docstring:    
   Return the orbit decomposition of "L" by the action of "cyc_act".

   INPUT:

   * "L" -- list
   * "cyc_act" -- bijective function from "L" to "L"

   OUTPUT:

   * a list of lists, the orbits under the cyc_act acting on "L"

which I have to import using

from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition

I am guessing that this function might be useful for other people, and will probably be reimplemented over and over again (it is not hard to do that, of course).

My question is: wouldn't it make sense to make it available in an easier way?  if so, how?

Martin

[David Joyner]

Yes, I agree it should be easier. But can't one simply call Gap's OrbitDomains
instead of reimplementing it?

> Martin
>
> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/b1532848-b1d6-426b-9312-66dba5d8ef5en%40googlegroups.com.

[Martin R]

I don't know about OrbitDomains, how does it work / how do you use it?

Is there a standard (and easy) way to define an action (in particular, a cyclic action) on a set in sage?

[David Joyner]

On Thu, Apr 28, 2022 at 9:35 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> I don't know about OrbitDomains, how does it work / how do you use it?
>

The documentation has an example:
https://www.gap-system.org/Manuals/doc/ref/chap41.html

> Is there a standard (and easy) way to define an action (in particular, a cyclic action) on a set in sage?
>

Sorry, I don't know an easy way. I've always just defined them by hand
whenever needed.
However, I agree with you that a better way is needed.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/626b9322-8fc4-49d8-bb53-638931f6057dn%40googlegroups.com.

[Linden Disney]

It is not perhaps easier, but an alternative way that I have used to calculate orbit decompsitions it to use 

from sage.groups.perm_gps.partn_ref.refinement_graphs import get_orbits

This works just by casting your group action as a subset of the permutation group action on the set. To define the action I (quite slowly) just acted via the group and found the corresponding index of the transformed element, so I agree a better way would be useful. 

[kcrisman]

On Thursday, April 28, 2022 at 11:26:12 AM UTC-4 David Joyner wrote:

On Thu, Apr 28, 2022 at 9:35 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> I don't know about OrbitDomains, how does it work / how do you use it?
>

The documentation has an example:
https://www.gap-system.org/Manuals/doc/ref/chap41.html

> Is there a standard (and easy) way to define an action (in particular, a cyclic action) on a set in sage?
>

Sorry, I don't know an easy way. I've always just defined them by hand
whenever needed.
However, I agree with you that a better way is needed.

I would love for there to be some standard way to define a group action on a set - preferably maintaining other algebraic properties of the set, such as addition!  But I don't know if there is even close to a standard way to do this either. 

[Travis Scrimshaw]

Sorry, I don't know an easy way. I've always just defined them by hand
whenever needed.
However, I agree with you that a better way is needed.

I would love for there to be some standard way to define a group action on a set - preferably maintaining other algebraic properties of the set, such as addition!  But I don't know if there is even close to a standard way to do this either. 

- There is a standard way to do this, but not a generic method/class for it IIRC. You can do this by implementing an _act_on_() method on a wrapper class. Yet, this requires some manual input.

- For cyclic actions, there is the DiscreteDynamicalSystem class introduced in https://trac.sagemath.org/ticket/24128.

- There is also the Representation class in modules/with_basis/representation.py if you want to want to extend the action on the set to the module with a basis given by that set.

Likely we will want to implement a class SetWithAction that automates a collects the orbit_decomposition functions and similar together as methods as a single global entry point.

Best,

Travis

[Martin R]

Would you be happy with something like the following, as a unifying and easily accessible framework?  Of course, I am thinking of providing also methods that convert it (back) into a representation, a combinatorial species, a permutation group.

class FiniteGroupAction(SageObject):

    def __init__(A, X=None, G=None):
    r"""
    A finite group action.

    INPUT:

    - ``A`` -- can be one of the following:

      * a permutation group, if ``X`` and ``G`` are ``None``

      * a bijection on a finite set ``X``, if ``G`` is ``None``

      * a map `G\times X\to X`, otherwise.

    - ``X`` (optional, default ``None``) -- a finite set

    - ``G`` (optional, default ``None``) -- a finite group

    EXAMPLES::

        sage: G = PermutationGroup([['b','c','a']], domain=['a','b','c','d'])
        sage: a = GroupAction(G)
        sage: a.orbits()
        [['a', 'b', 'c'], ['d']]

        sage: A = lambda x: (2*x) % 6
        sage: X = [0,1,2,3,4,5]
        sage: a = GroupAction(A, X)
        sage: a.orbits()
        [[0], [1, 2, 4], [3], [5]]

        sage: G = SymmetricGroup(3)
        sage: A = lambda g, x: g*x
        sage: a = GroupAction(A, G, G)
        sage: a.orbits()
        [['a', 'b', 'c', 'd']]

[David Joyner]

1) This is okay with me, but by "set" I assume you don't mean "Set":-)
For example,

sage: A = lambda g, x: g*x

sage: G = SL(2,5)
sage: X = GF(5)^2
sage: a = GroupAction(A, X, G)
sage: a.orbits()
should return something reasonable.
2) Your new class should be consistent with the built in action
of permutation groups and automorphism groups on various
objects (eg, graphs, block designs, incidence structures)
It would be nice if there could be a default "A" in this
case.

Some examples of such built-in orbits,

sage: A = lambda g, x: g*x

sage: X = [1,2,3,4]
sage: G = SymmetricGroup(X)
sage: H = G.subgroup([[(1,2),(3,4)]]);
sage: a = GroupAction(A, H, X)
sage: a.orbits()
should be consistent with the built in permutation group action
sage: X = [1,2,3,4]
sage: G = SymmetricGroup(X)
sage: H = G.subgroup([[(1,2),(3,4)]]); H.list()
[(), (1,2)(3,4)]
sage: H.orbits()
[[1, 2], [3, 4]]
and

sage: A = lambda g, x: g*x

sage: X = graphs.ButterflyGraph()
sage: G = Gamma.automorphism_group()
sage: a = GroupAction(A, G, Gamma)
sage: a.orbits()
should give more or less the same output as
sage: Gamma = graphs.ButterflyGraph()
sage: G = Gamma.automorphism_group()
sage: G.orbits()
[[0, 1, 2, 3], [4]]
However, I'm not sure how your class would yield the output of
sage: P = designs.DesarguesianProjectivePlaneDesign(2)
sage: G = P.automorphism_group()
sage: G.orbits()
[[(0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 0, 0), (1, 1, 1), (0, 1, 0), (1, 1, 0)]]

> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/20c36129-bd92-4252-9a85-a750aea7b038n%40googlegroups.com.

[Martin R]

At https://trac.sagemath.org/ticket/33784 there is a minimal working skeleton class.

On Monday, 2 May 2022 at 12:35:29 UTC+2 David Joyner wrote:

1) This is okay with me, but by "set" I assume you don't mean "Set":-)

I don't understand what you mean here.  The elements of X should be hashable, I guess.

 

For example,
sage: A = lambda g, x: g*x
sage: G = SL(2,5)
sage: X = GF(5)^2
sage: a = GroupAction(A, X, G)
sage: a.orbits()
should return something reasonable.

            sage: A = lambda g, x: vector(g*x, immutable=True)
            sage: G = SL(2,3)
            sage: X = [vector(x, immutable=True) for x in GF(3)^2]
            sage: a = FiniteGroupAction(A, X, G)
            sage: a.orbits()
            [[(0, 0)], [(1, 0), (0, 2), (2, 2), (2, 0), (1, 2), (2, 1), (0, 1), (1, 1)]]

 

2) Your new class should be consistent with the built in action
of permutation groups and automorphism groups on various
objects (eg, graphs, block designs, incidence structures)
It would be nice if there could be a default "A" in this
case.

Some examples of such built-in orbits,
sage: A = lambda g, x: g*x
sage: X = [1,2,3,4]
sage: G = SymmetricGroup(X)
sage: H = G.subgroup([[(1,2),(3,4)]]);
sage: a = GroupAction(A, H, X)
sage: a.orbits()
should be consistent with the built in permutation group action
sage: X = [1,2,3,4]
sage: G = SymmetricGroup(X)
sage: H = G.subgroup([[(1,2),(3,4)]]); H.list()
[(), (1,2)(3,4)]
sage: H.orbits()
[[1, 2], [3, 4]]

If you already have a permutation group, you'd just say FiniteGroupAction(H).

 

and
sage: A = lambda g, x: g*x
sage: X = graphs.ButterflyGraph()
sage: G = Gamma.automorphism_group()
sage: a = GroupAction(A, G, Gamma)
sage: a.orbits()
should give more or less the same output as
sage: Gamma = graphs.ButterflyGraph()
sage: G = Gamma.automorphism_group()
sage: G.orbits()
[[0, 1, 2, 3], [4]]

same here.

 

However, I'm not sure how your class would yield the output of
sage: P = designs.DesarguesianProjectivePlaneDesign(2)
sage: G = P.automorphism_group()
sage: G.orbits()
[[(0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 0, 0), (1, 1, 1), (0, 1, 0), (1, 1, 0)]]

same here.

[kcrisman]

Hmm, maybe a tutorial is needed for this.  I would imagine that a lot of people who aren't familiar with how to create a new wrapper class would be the ones who need this.   Of course, the FiniteGroupAction suggestion sounds quite welcome, too, though really having both options would be best.

[Martin R]

I am actually not sure anymore, which methods or functionality this class should provide.

Would it possibly be better to enhance PermutationGroup with an additional optional "from_action" and "from_cyclic_action" argument?  Eg.:

PermutationGroup(domain = X, cyclic_action = lambda x: f(x))

PermutationGroup(domain = X, group_action = (G, lambda g, x: f(g, x)))

Martin

[David Joyner]

On Mon, May 2, 2022 at 11:24 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> I am actually not sure anymore, which methods or functionality this class should provide.
>
> Would it possibly be better to enhance PermutationGroup with an additional optional "from_action" and "from_cyclic_action" argument? Eg.:
>
> PermutationGroup(domain = X, cyclic_action = lambda x: f(x))
>
> PermutationGroup(domain = X, group_action = (G, lambda g, x: f(g, x)))
>

I like this idea!

> Martin
> On Monday, 2 May 2022 at 14:20:57 UTC+2 kcrisman wrote:
>>
>> On Sunday, May 1, 2022 at 7:32:01 PM UTC-4 Travis Scrimshaw wrote:
>>>>>
>>>>> Sorry, I don't know an easy way. I've always just defined them by hand
>>>>> whenever needed.
>>>>> However, I agree with you that a better way is needed.
>>>>
>>>>
>>>> I would love for there to be some standard way to define a group action on a set - preferably maintaining other algebraic properties of the set, such as addition! But I don't know if there is even close to a standard way to do this either.
>>>
>>>
>>> - There is a standard way to do this, but not a generic method/class for it IIRC. You can do this by implementing an _act_on_() method on a wrapper class. Yet, this requires some manual input.
>>> - For cyclic actions, there is the DiscreteDynamicalSystem class introduced in https://trac.sagemath.org/ticket/24128.
>>> - There is also the Representation class in modules/with_basis/representation.py if you want to want to extend the action on the set to the module with a basis given by that set.
>>>
>>> Likely we will want to implement a class SetWithAction that automates a collects the orbit_decomposition functions and similar together as methods as a single global entry point.
>>>
>>
>> Hmm, maybe a tutorial is needed for this. I would imagine that a lot of people who aren't familiar with how to create a new wrapper class would be the ones who need this. Of course, the FiniteGroupAction suggestion sounds quite welcome, too, though really having both options would be best.
>

> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/694a16d8-b59d-43bc-8b68-033c704284abn%40googlegroups.com.

[Martin R]

I implemented (well, the implementation is trivial) the following, and I'd like feedback.  I am not completely sure whether the interface for the second variant, where the generators of the acting group are required, is ideal, but I think it looks useable.

A more serious problem is that orbits are currently computed twice: once when creating the generators of the permutation group, and another time, when asking for them.

Martin

    """

    ...

    We can create a permutation group from a group action::

        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), (0, 2), (2, 2), (2, 0), (1, 2), (2, 1), (0, 1), (1, 1)]]

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

    ...

    """

    if not is_ExpectElement(gens) and hasattr(gens, '_permgroup_'):
        return gens._permgroup_()
    if gens is not None and not isinstance(gens, (tuple, list, GapElement)):
        raise TypeError("gens must be a tuple, list, or GapElement")
    gap_group = kwds.get("gap_group", None)
    domain = kwds.get("domain", None)
    canonicalize = kwds.get("canonicalize", True)
    category = kwds.get("category", None)
    action = kwds.get("action", None)
    if action is not None:
        if domain is None:
            raise ValueError("you must specify the domain for an action")
        from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
        if gap_group is not None:
            raise ValueError("gap_group is not supported with action")
        if gens is None and gap_group is None:
            gens = [tuple(o) for o in orbit_decomposition(domain, action)]
        else:
            gens = [[tuple(o) for o in orbit_decomposition(domain, lambda x: action(g, x))]
                    for g in gens]
    if args:
        from sage.misc.superseded import deprecation
        deprecation(31510, "gap_group, domain, canonicalize, category will become keyword only")
        if len(args) > 4:
            raise ValueError("invalid input")
        args = list(args)
        gap_group = args.pop(0)
        if args:
            domain = args.pop(0)
            if args:
                canonicalize = args.pop(0)
                if args:
                    category = args.pop(0)
    return PermutationGroup_generic(gens=gens, gap_group=gap_group, domain=domain,
                                    canonicalize=canonicalize, category=category)

[kcrisman]

On Monday, May 2, 2022 at 11:24:44 AM UTC-4 axio...@yahoo.de wrote:

I am actually not sure anymore, which methods or functionality this class should provide.

Would it possibly be better to enhance PermutationGroup with an additional optional "from_action" and "from_cyclic_action" argument?  Eg.:

PermutationGroup(domain = X, cyclic_action = lambda x: f(x))

PermutationGroup(domain = X, group_action = (G, lambda g, x: f(g, x)))

I'm thinking here also of actions on other sets, though, which wouldn't just be a matrix representation, unless I'm misunderstanding the purpose of these function signatures.   In particular, an action of a group on set of vectors, which stay vectors.  Examples:

* Permutation group of 3 elements on 3-vectors in obvious manner

* Permutation group of 3 elements on 6-vectors in non-obvious manner where they are indexed [e,(12),(13),(23),(123),(132)] or something like that

[Martin R]

Won't you be better off thinking of it as a representation, then?

What would you like sage to do for you when working with a group action on an infinite set?

Martin

[Martin R]

There is now an approach using a subclass of permutationgroup on trac

Comments would be great!

[David Joyner]

On Tue, May 3, 2022 at 7:12 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> I implemented (well, the implementation is trivial) the following, and I'd like feedback. I am not completely sure whether the interface for the second variant, where the generators of the acting group are required, is ideal, but I think it looks useable.
>
> A more serious problem is that orbits are currently computed twice: once when creating the generators of the permutation group, and another time, when asking for them.
>
> Martin
>

Hi Martin:

Thanks for programming this. I'd like to test it's functionality but
don't know your function's syntax. Something like

def PermutationGroup2(gens=None, gap_group=None, domain=None,
canonicalize=True, category=None, action=None):

maybe?

- David

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/641f204b-f89c-49f5-97d2-4ce8741ef04cn%40googlegroups.com.

[Martin R]

You just need to git Trac try the branch, there are examples in the docstring of PermutationGroup

[Martin R]

https://trac.sagemath.org/ticket/33784 is now ready for review.

I am still open for discussion, of course.  In particular, we might want to discuss whether we should also provide a separate class which models a group action, and not only the homomorphic image of the acting group.

Martin

[kcrisman]

On Tuesday, May 3, 2022 at 7:48:07 AM UTC-4 axio...@yahoo.de wrote:

Won't you be better off thinking of it as a representation, then?

Correct, but I don't know how to construct those on arbitrary vector spaces in Sage.  That is to say, if I know the vector space, and I know the action, but it's not some well-known one like the permutation representation on a finite set by the symmetric group on that set. 

[David Joyner]

On Wed, May 4, 2022 at 5:02 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> https://trac.sagemath.org/ticket/33784 is now ready for review.
>

Thank you!

Here's another example, for those following this thread:

sage: A = lambda g, x: g(x)

sage: Gamma = graphs.ButterflyGraph()
sage: G = Gamma.automorphism_group()

sage: H = PermutationGroup(G.gens(), action=A, domain=Gamma.vertices())
sage: H.orbits()

[[0, 1, 2, 3], [4]]
sage: G.orbits()
[[0, 1, 2, 3], [4]]

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/46e0ca70-1be0-469d-bafc-b35117b9f5d1n%40googlegroups.com.

[Martin R]

I am guessing that Travis'  Representation class does the trick, but I have to figure out how to use it.

[Martin R]

David, could you do the review?

[David Joyner]

On Thu, May 5, 2022 at 3:51 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> David, could you do the review?
>

I don't know git but, for my own amusement, I copy+pasted all
the code in that module on your trac ticket into a sage file, then
attached it to a sage session and ran some examples.
I'd be happy to test all the doc examples "by hand" if that helps any.

> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/3d812171-c0df-46f7-880d-a4f4d4ea2343n%40googlegroups.com.

[Martin R]

I guess you would have to read the code and make sure that you think it is OK, possibly ask for clarifications or better examples, and then select "positive review" on the trac ticket.

[David Joyner]

On Thu, May 5, 2022 at 7:59 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> I guess you would have to read the code and make sure that you think it is OK, possibly ask for clarifications or better examples, and then select "positive review" on the trac ticket.
>

Will do.

> On Thursday, 5 May 2022 at 11:06:15 UTC+2 David Joyner wrote:
>>
>> On Thu, May 5, 2022 at 3:51 AM 'Martin R' via sage-devel
>> <sage-...@googlegroups.com> wrote:
>> >
>> > David, could you do the review?
>> >
>>
>> I don't know git but, for my own amusement, I copy+pasted all
>> the code in that module on your trac ticket into a sage file, then
>> attached it to a sage session and ran some examples.
>> I'd be happy to test all the doc examples "by hand" if that helps any.
>>
>> > On Wednesday, 4 May 2022 at 14:26:49 UTC+2 Martin R wrote:
>> >>
>> >> I am guessing that Travis' Representation class does the trick, but I have to figure out how to use it.
>> >> On Wednesday, 4 May 2022 at 13:40:07 UTC+2 kcrisman wrote:
>> >>>
>> >>> On Tuesday, May 3, 2022 at 7:48:07 AM UTC-4 axio...@yahoo.de wrote:
>> >>>>
>> >>>> Won't you be better off thinking of it as a representation, then?
>> >>>>
>> >>>
>> >>> Correct, but I don't know how to construct those on arbitrary vector spaces in Sage. That is to say, if I know the vector space, and I know the action, but it's not some well-known one like the permutation representation on a finite set by the symmetric group on that set.
>> >
>> > --
>> > 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/3d812171-c0df-46f7-880d-a4f4d4ea2343n%40googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/96607c03-3328-4385-a876-b031f0d16de0n%40googlegroups.com.