Opened 4 years ago

Closed 4 years ago

#19613 closed enhancement (fixed)

Implement basic representations of semigroups

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.1
Component: group theory Keywords: representation, semigroups,
Cc: sage-combinat, nthiery, virmaux Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: f8b1e30 (Commits) Commit: f8b1e3040199be23644dc67c4236018bf6a89b8f
Dependencies: Stopgaps:

Description

We provide a basic implementation of representations of semigroups with a distinguished basis.

Change History (30)

comment:1 Changed 4 years ago by tscrim

  • Branch set to public/representations/basic_implementation-19613
  • Commit set to 0d510228773b6f7899c09e405f93a963595f0af0
  • Status changed from new to needs_review

This is a first step to an implementation of group (co)homology.


New commits:

0d51022Initial implementation of representations of a semigroup.

comment:2 follow-up: Changed 4 years ago by darij

This is promising to be really useful!

A few first impressions (Sage is compiling doc, so I can't really edit):

Can you document the left_repr keyword in the regular_representation method in semigroups.py?

In the _acted_upon_ of TrivialRepresentation, I would use a sum method instead of the sum function (I hope it would involve less indirection/ducktyping).

Does the RegularRepresentation allow both multiplying by elements of the semigroup and multiplying by elements of the semigroup algebra? (And if so, please doctest both.)

I have recently wrotten some really sloppy code to build a finite semigroup out of a multiplication table (I hoped to use it on #19892, but then I found that semigroups lack the support for that, so I ended up avoiding it). I'm wondering -- would this be useful for this patch? At the very least it could give us a way to doctest the methods. I could polish the code and submit it here; I just want to make sure it won't be in vain, as I have a hard time believing that there is no such thing in Sage already...

Last edited 4 years ago by darij (previous) (diff)

comment:3 Changed 4 years ago by git

  • Commit changed from 0d510228773b6f7899c09e405f93a963595f0af0 to 9f2ff6e14f3376d420dbe87715a0bd112e0ccdb7

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

34e496eMerge branch 'public/representations/basic_implementation-19613' of trac.sagemath.org:sage into public/representations/basic_implementation-19613
9f2ff6eFixing doctests, adding doctests, and fixing some bugs with _acted_upon_.

comment:4 in reply to: ↑ 2 ; follow-up: Changed 4 years ago by tscrim

Replying to darij:

Can you document the left_repr keyword in the regular_representation method in semigroups.py?

Added.

In the _acted_upon_ of TrivialRepresentation, I would use a sum method instead of the sum function (I hope it would involve less indirection/ducktyping).

That isn't ducktyping (it's the python sum not the symbolic sum that is at the top-level interface). Also, all self.base_ring().sum(elts) does is call sum(elts, self.zero()) so it involves one further level of indirection.

Does the RegularRepresentation allow both multiplying by elements of the semigroup and multiplying by elements of the semigroup algebra? (And if so, please doctest both.)

Yes, and I added some doctests about this. I also caught a few bugs with these doctests.

I have recently wrotten some really sloppy code to build a finite semigroup out of a multiplication table (I hoped to use it on #19892, but then I found that semigroups lack the support for that, so I ended up avoiding it). I'm wondering -- would this be useful for this patch? At the very least it could give us a way to doctest the methods. I could polish the code and submit it here; I just want to make sure it won't be in vain, as I have a hard time believing that there is no such thing in Sage already...

There is code in algebras/finite_dimensional_algebras which essentially does that. We probably could separate that code into the semigroup part and the algebra part (and combine it with your code). However, I think that is better for a separate ticket because it won't directly apply to this (could be good for extensive testing of this, but I think that could be overkill).

comment:5 Changed 4 years ago by nthiery

Hmm, I really need to get my pile of semigroup code into Sage. But this should not stop you from making progress in the mean time. In case you'd have the occasion to spend a couple days in Paris, I'd be happy to do a coding sprint with you on this topic.

For building a variety of semigroups, you can use sage.monoids.automatic_semigroup.AutomaticSemigroup.

For info: I am currently working on an improved GAP-Sage interface allowing to easily wrap all kind of GAP parents, including semigroups:

https://github.com/nthiery/sage-gap-semantic-interface

But here again, don't hold your breath!

Cheers,

comment:6 in reply to: ↑ 4 Changed 4 years ago by darij

  • Keywords semigroups added
  • Milestone changed from sage-6.10 to sage-7.1

Replying to tscrim:

Replying to darij:

Can you document the left_repr keyword in the regular_representation method in semigroups.py?

Added.

OK, weird. Why do you call it left one time and left_repr another? Also, it is still undocumented one time in semigroups.py (there are two regular_representation methods in that file; sorry for missing that).

In the _acted_upon_ of TrivialRepresentation, I would use a sum method instead of the sum function (I hope it would involve less indirection/ducktyping).

That isn't ducktyping (it's the python sum not the symbolic sum that is at the top-level interface). Also, all self.base_ring().sum(elts) does is call sum(elts, self.zero()) so it involves one further level of indirection.

Ah, you're perfectly right.

I have recently wrotten some really sloppy code to build a finite semigroup out of a multiplication table (I hoped to use it on #19892, but then I found that semigroups lack the support for that, so I ended up avoiding it). I'm wondering -- would this be useful for this patch? At the very least it could give us a way to doctest the methods. I could polish the code and submit it here; I just want to make sure it won't be in vain, as I have a hard time believing that there is no such thing in Sage already...

There is code in algebras/finite_dimensional_algebras which essentially does that. We probably could separate that code into the semigroup part and the algebra part (and combine it with your code). However, I think that is better for a separate ticket because it won't directly apply to this (could be good for extensive testing of this, but I think that could be overkill).

I guess you're right -- groups are probably enough for doctesting.

I am aware of algebras/finite_dimensional_algebras being essentially the linear version of what I wanted to do. (This is what I ended up using in #19892, since I really cared about the face semigroup algebra, not the face semigroup.) Still I wanted the non-linear version, since having a semigroup algebra without its semigroup looks really weird.

Nicolas, is this something you have in your code?

Last edited 4 years ago by darij (previous) (diff)

comment:7 Changed 4 years ago by git

  • Commit changed from 9f2ff6e14f3376d420dbe87715a0bd112e0ccdb7 to 99de16fca5c2c66b622a358c4de577f165aa7718

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

99de16fChanging left_repr -> repr so I am consistent.

comment:8 follow-up: Changed 4 years ago by tscrim

@darij Now both methods use left and are documented.

What I am suggesting is refactor the multiplication code for the fin-dim algebras into a finite semigroup (well, really finite magma because the product does not have to be associative). Then we would make a fin-dim algebra to be the algebra of a finite semigroup (magma).

@nthiery I will should have some time before (and I think after but need to double-check) Days 74, and I would be happy to do some coding sprints with you.

PS - How were the Sage-GAP days?

Last edited 4 years ago by tscrim (previous) (diff)

comment:9 in reply to: ↑ 8 Changed 4 years ago by nthiery

Replying to tscrim:

What I am suggesting is refactor the multiplication code for the fin-dim algebras into a finite semigroup (well, really finite magma because the product does not have to be associative). Then we would make a fin-dim algebra to be the algebra of a finite semigroup (magma).

This is for darij specific use case, right? Not all fin dim algebra come from a finite semigroup/magma.

@nthiery I will should have some time before (and I think after but need to double-check) Days 74, and I would be happy to do some coding sprints with you.

Sounds good!

PS - How were the Sage-GAP days?

It was good to meet and share with the GAP people. And to have time to focus on one coding sprint!

comment:10 Changed 4 years ago by git

  • Commit changed from 99de16fca5c2c66b622a358c4de577f165aa7718 to 38529351ae5581559a6a33a6fc6fe825b974ef81

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

287058bMerge branch 'public/representations/basic_implementation-19613' of git://trac.sagemath.org/sage into rep
41bc62cfix left_repr names and expose some properties
3852935more doc

comment:11 follow-up: Changed 4 years ago by darij

I've reviewed the ticket up to TrivialRepresentation. However, exposing self._module the way I've done it is incompatible with your implementation of TrivialRepresentation, and this is a design question I feel is in need of discussion. What do you think is the right way?

  1. Unexpose self._module, since any method that uses linear algebra on self._module can just as well use it on self.
  1. Set self._module = self for a TrivialRepresentation.
  1. Implement TrivialRepresentation using the general Representation constructor.

I don't see anything wrong with either of these options, but I am not the one to judge. A caveat with 1 is that coders need to be dissuaded from using self._module in their code (and this is a tricky thing to do, because not everyone will have a TrivialRepresentation in their doctests). Option 2 might incur endless loops or unwanted memory persistence, but I don't know. Option 3 feels like overkill, but it's the most straightforward thing.

Speaking of endless loops, do you have an idea why this gives one?

sage: G = groups.permutation.Dihedral(4)
sage: R = G.regular_representation(left=False)
sage: x = R.an_element()
sage: x*x

Oh, and one more thing. I think TrivialRepresentation might need a left option. Even if the action itself doesn't care, future code might (e.g., taking the direct sum of two representations might start off by checking whether both have the same left-right-ness, and tada you've got a pointless error when you try to add a right representation to the trivial one).

Last edited 4 years ago by darij (previous) (diff)

comment:12 in reply to: ↑ 11 ; follow-up: Changed 4 years ago by tscrim

Replying to darij:

I've reviewed the ticket up to TrivialRepresentation.

Thank you for doing the review. (I guess I should review your face semigroup ticket...)

However, exposing self._module the way I've done it is incompatible with your implementation of TrivialRepresentation, and this is a design question I feel is in need of discussion. What do you think is the right way?

  1. Unexpose self._module, since any method that uses linear algebra on self._module can just as well use it on self.
  1. Set self._module = self for a TrivialRepresentation.
  1. Implement TrivialRepresentation using the general Representation constructor.

I would go with 1. I did not expose it because the representation behaves like a module (you better not say something about ducktyping here) and it is there only for internal use. You're getting to one of the reasons why TrivialRepresentation is not a subclass of Representation. If you really feel that it should be exposed, then I would have module() return self so there is a consistent API. (Unfortunately I don't think we have the infrastructure in place to setup the necessary coercions.)

Speaking of endless loops, do you have an idea why this gives one?

sage: G = groups.permutation.Dihedral(4)
sage: R = G.regular_representation(left=False)
sage: x = R.an_element()
sage: x*x

No, and from the code, there does not seem to be a reason why this should happen. (This should result in an error though.) I will investigate this.

Oh, and one more thing. I think TrivialRepresentation might need a left option. Even if the action itself doesn't care, future code might (e.g., taking the direct sum of two representations might start off by checking whether both have the same left-right-ness, and tada you've got a pointless error when you try to add a right representation to the trivial one).

If future code cares, then the future code can deal with creating the error/extra complexity. However, we can consider it as simultaneously a right and left representation, so I don't think this would be an issue.

Actually, given these recent changes, it reminded me why I had left_repr. I actually think left_repr is more descriptive, and so we should change all of the left to left_repr. Your thoughts?

comment:13 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by darij

Replying to tscrim:

Replying to darij:

I've reviewed the ticket up to TrivialRepresentation.

Thank you for doing the review. (I guess I should review your face semigroup ticket...)

I think that's already (almost) done, but thank you :)

I would go with 1. I did not expose it because the representation behaves like a module (you better not say something about ducktyping here) and it is there only for internal use. You're getting to one of the reasons why TrivialRepresentation is not a subclass of Representation. If you really feel that it should be exposed, then I would have module() return self so there is a consistent API. (Unfortunately I don't think we have the infrastructure in place to setup the necessary coercions.)

Wait, what? TrivialRepresentation does not inherit from Representation? This I really don't like. Particularly if you don't expose self._module, there should be no reason to keep the trivial one out of it.

I have thought about these things again and here are my suggestions:

S1. It is fine for Representation to treat self._module as an implementation detail that might not get inherited, but please document this in the init sourcecode (just a # comment saying that self._module might not exist).

S2. Please document in the docstring that the trivial representation is both left and right.

S3. At some point we will need a way to tell if a given representation is left or right. I think this should be a property (not underscored) which is a boolean or None (for two-sided). Do you agree?

S4. In the _acted_upon_ of TrivialRepresentation, does _from_dict(d) do the right thing when d == 0 ?

Speaking of endless loops, do you have an idea why this gives one?

sage: G = groups.permutation.Dihedral(4)
sage: R = G.regular_representation(left=False)
sage: x = R.an_element()
sage: x*x

No, and from the code, there does not seem to be a reason why this should happen. (This should result in an error though.) I will investigate this.

Yes, it should result in an error, just not in an exceeded recursion limit. Not a bug per se, but hell does it smell fishy. Then again, a quick look at the implementation of coercion in parent.pyx convinced me to be amazed at the fact that coercion works at all... (EDIT for clarity: In no way does this need to be solved for a positive review of this ticket; this is really a different story.)

If future code cares, then the future code can deal with creating the error/extra complexity. However, we can consider it as simultaneously a right and left representation, so I don't think this would be an issue.

Agreed -- just wanting it to be explicit.

Actually, given these recent changes, it reminded me why I had left_repr. I actually think left_repr is more descriptive, and so we should change all of the left to left_repr. Your thoughts?

I'm fine with left_repr or with anything, as long as it is the same keyword everywhere.

Last edited 4 years ago by darij (previous) (diff)

comment:14 in reply to: ↑ 13 ; follow-up: Changed 4 years ago by tscrim

Replying to darij:

Replying to tscrim:

I would go with 1. I did not expose it because the representation behaves like a module (you better not say something about ducktyping here) and it is there only for internal use. You're getting to one of the reasons why TrivialRepresentation is not a subclass of Representation. If you really feel that it should be exposed, then I would have module() return self so there is a consistent API. (Unfortunately I don't think we have the infrastructure in place to setup the necessary coercions.)

Wait, what? TrivialRepresentation does not inherit from Representation? This I really don't like. Particularly if you don't expose self._module, there should be no reason to keep the trivial one out of it.

Why should it? They are completely different implementations. This isn't even ducktyping, it is just about having a common API because all it is really about is just overloading *. However, after thinking about it a bit, there is some benefit for having a common base class for Representation and TrivialRepresentation, but there is no strong reason to force common base classes. (Ideally, this would be handled with a category, but I think we need more discussion and examples to see what the best way to do this will be.)

I have thought about these things again and here are my suggestions:

S1. It is fine for Representation to treat self._module as an implementation detail that might not get inherited, but please document this in the init sourcecode (just a # comment saying that self._module might not exist).

self._module will always exist because TrivialRepresentation will not inherit from Representation. Representation is a slight variant of what is sometimes called a decorator pattern, whereas TrivialRepresentation is a direct subclass of CFM. As they have very different implementations, there should not be a subclass relationship Representation to TrivialRepresentation.

S2. Please document in the docstring that the trivial representation is both left and right.

Will do.

S3. At some point we will need a way to tell if a given representation is left or right. I think this should be a property (not underscored) which is a boolean or None (for two-sided). Do you agree?

If anything, this should be a method, not an (hidden) attribute. However, I do agree we need something. Althought AFAIK this is the first time we have a left but not necessarily a right module.

S4. In the _acted_upon_ of TrivialRepresentation, does _from_dict(d) do the right thing when d == 0 ?

This will never happen as monomial_coefficients returns a dict. However, I do see a potential when acting on the zero element. I will check/doctest this.

(I'm waiting for 7.1.beta1 to come out before I make any changes. You know as soon as I bump my Sage to beta0, beta1 will be released...)

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by darij

Replying to tscrim:

Replying to darij:

Wait, what? TrivialRepresentation does not inherit from Representation? This I really don't like. Particularly if you don't expose self._module, there should be no reason to keep the trivial one out of it.

Why should it? They are completely different implementations.

Implementations yes, but the underlying concepts should be of the same type. One of the next steps will be a direct sum of two representations, for example. You do want to be able to add a regular and a trivial representation, I assume?

S3. At some point we will need a way to tell if a given representation is left or right. I think this should be a property (not underscored) which is a boolean or None (for two-sided). Do you agree?

If anything, this should be a method, not an (hidden) attribute. However, I do agree we need something. Althought AFAIK this is the first time we have a left but not necessarily a right module.

S4. In the _acted_upon_ of TrivialRepresentation, does _from_dict(d) do the right thing when d == 0 ?

This will never happen as monomial_coefficients returns a dict. However, I do see a potential when acting on the zero element. I will check/doctest this.

You multiply all the entries of that dict with sum(scalar.coefficients()). If this sum is 0, then it's suddenly a dict full of zeroes.

(I'm waiting for 7.1.beta1 to come out before I make any changes. You know as soon as I bump my Sage to beta0, beta1 will be released...)

I know that feeling :)

Last edited 4 years ago by darij (previous) (diff)

comment:16 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by tscrim

Replying to darij:

Replying to tscrim:

Replying to darij:

Wait, what? TrivialRepresentation does not inherit from Representation? This I really don't like. Particularly if you don't expose self._module, there should be no reason to keep the trivial one out of it.

Why should it? They are completely different implementations.

Implementations yes, but the underlying concepts should be of the same type. One of the next steps will be a direct sum of two representations, for example. You do want to be able to add a regular and a trivial representation, I assume?

That is more about having a common API. Anyways, Representation and TrivialRepresentation will have a common ABC, so I think this issue is moot.

S4. In the _acted_upon_ of TrivialRepresentation, does _from_dict(d) do the right thing when d == 0 ?

This will never happen as monomial_coefficients returns a dict. However, I do see a potential when acting on the zero element. I will check/doctest this.

You multiply all the entries of that dict with sum(scalar.coefficients()). If this sum is 0, then it's suddenly a dict full of zeroes.

_from_dict has an optional argument to check for removing zeros (whose default is True). So this isn't an issue.

(I'm waiting for 7.1.beta1 to come out before I make any changes. You know as soon as I bump my Sage to beta0, beta1 will be released...)

I know that feeling :)

It is just released in fact.

comment:17 in reply to: ↑ 16 Changed 4 years ago by darij

Replying to tscrim:

Replying to darij:

Replying to tscrim:

Replying to darij:

Wait, what? TrivialRepresentation does not inherit from Representation? This I really don't like. Particularly if you don't expose self._module, there should be no reason to keep the trivial one out of it.

Why should it? They are completely different implementations.

Implementations yes, but the underlying concepts should be of the same type. One of the next steps will be a direct sum of two representations, for example. You do want to be able to add a regular and a trivial representation, I assume?

That is more about having a common API. Anyways, Representation and TrivialRepresentation will have a common ABC, so I think this issue is moot.

Ah, perfect.

S4. In the _acted_upon_ of TrivialRepresentation, does _from_dict(d) do the right thing when d == 0 ?

This will never happen as monomial_coefficients returns a dict. However, I do see a potential when acting on the zero element. I will check/doctest this.

You multiply all the entries of that dict with sum(scalar.coefficients()). If this sum is 0, then it's suddenly a dict full of zeroes.

_from_dict has an optional argument to check for removing zeros (whose default is True). So this isn't an issue.

Oh! I forgot the semantics of _from_dict; so it's not as low-level as I expected. You are right!

comment:18 Changed 4 years ago by git

  • Commit changed from 38529351ae5581559a6a33a6fc6fe825b974ef81 to 446f369a6e1bdaaa94e607db4285353e1a7f5438

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

9f24c9dMerge branch 'develop' into public/representations/basic_implementation-19613
acab27bMerge branch 'public/representations/basic_implementation-19613' of trac.sagemath.org:sage into public/representations/basic_implementation-19613
446f369Refactoring and adding some documentation as per Darij's comments.

comment:19 Changed 4 years ago by tscrim

Taken care of all of the above.

The x * x issue appears with just a combinatorial free module:

sage: C = CombinatorialFreeModule(ZZ, ['a','b'])
sage: x = C.an_element()
sage: x * x  # BOOM

so it is unrelated to this ticket.

comment:20 follow-up: Changed 4 years ago by nthiery

Just a tiny comment: please use side="left" rather than left=True, for consistency with what's done elsewhere (Coxeter groups, cayley graphs, ...).

Cheers,

comment:21 Changed 4 years ago by git

  • Commit changed from 446f369a6e1bdaaa94e607db4285353e1a7f5438 to 51ae764bac944dcfaf7959000eac6d137ab3f2d4

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

51ae764left_repr -> side.

comment:22 in reply to: ↑ 20 Changed 4 years ago by tscrim

Replying to nthiery:

Just a tiny comment: please use side="left" rather than left=True, for consistency with what's done elsewhere (Coxeter groups, cayley graphs, ...).

Done. I also added a method to Representation exposing the side.

comment:23 Changed 4 years ago by git

  • Commit changed from 51ae764bac944dcfaf7959000eac6d137ab3f2d4 to 3a89f371c3346f1a6528bb8722570412ad1a50cc

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

3a89f37minor doc improvements, -1 bug

comment:24 Changed 4 years ago by darij

Shouldn't the side method be on the ABC rather than on the implementation? (It might well be an abstract method, but it should be available, at least if we are serious about the ABC.)

As far as everything else is concerned, this LGTM!


New commits:

3a89f37minor doc improvements, -1 bug

New commits:

3a89f37minor doc improvements, -1 bug

comment:25 Changed 4 years ago by git

  • Commit changed from 3a89f371c3346f1a6528bb8722570412ad1a50cc to 3e6a1f6f2b5090799cc0763fc54aef05849c357b

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

3e6a1f6Added side to ABC and trivial representation because ABCs need to be completely complete.

comment:26 Changed 4 years ago by git

  • Commit changed from 3e6a1f6f2b5090799cc0763fc54aef05849c357b to f8b1e3040199be23644dc67c4236018bf6a89b8f

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

f8b1e30One last tweak with the side input.

comment:27 Changed 4 years ago by darij

  • Reviewers set to Darij Grinberg

Thank you! The code now LGTM. Does it LGTY?

comment:28 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

Yes. Thank you for doing the review.

comment:29 Changed 4 years ago by darij

Thanks for one of the most useful 500-line patches Sage has!

comment:30 Changed 4 years ago by vbraun

  • Branch changed from public/representations/basic_implementation-19613 to f8b1e3040199be23644dc67c4236018bf6a89b8f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.