Opened 4 years ago
Closed 4 years ago
#19613 closed enhancement (fixed)
Implement basic representations of semigroups
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage7.1 
Component:  group theory  Keywords:  representation, semigroups, 
Cc:  sagecombinat, 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
 Branch set to public/representations/basic_implementation19613
 Commit set to 0d510228773b6f7899c09e405f93a963595f0af0
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 4 years ago by
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...
comment:3 Changed 4 years ago by
 Commit changed from 0d510228773b6f7899c09e405f93a963595f0af0 to 9f2ff6e14f3376d420dbe87715a0bd112e0ccdb7
comment:4 in reply to: ↑ 2 ; followup: ↓ 6 Changed 4 years ago by
Replying to darij:
Can you document the
left_repr
keyword in theregular_representation
method insemigroups.py
?
Added.
In the
_acted_upon_
ofTrivialRepresentation
, I would use asum
method instead of thesum
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 toplevel 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
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 GAPSage interface allowing to easily wrap all kind of GAP parents, including semigroups:
But here again, don't hold your breath!
Cheers,
comment:6 in reply to: ↑ 4 Changed 4 years ago by
 Keywords semigroups added
 Milestone changed from sage6.10 to sage7.1
Replying to tscrim:
Replying to darij:
Can you document the
left_repr
keyword in theregular_representation
method insemigroups.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_
ofTrivialRepresentation
, I would use asum
method instead of thesum
function (I hope it would involve less indirection/ducktyping).That isn't ducktyping (it's the python
sum
not the symbolicsum
that is at the toplevel interface). Also, allself.base_ring().sum(elts)
does is callsum(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 nonlinear version, since having a semigroup algebra without its semigroup looks really weird.
Nicolas, is this something you have in your code?
comment:7 Changed 4 years ago by
 Commit changed from 9f2ff6e14f3376d420dbe87715a0bd112e0ccdb7 to 99de16fca5c2c66b622a358c4de577f165aa7718
Branch pushed to git repo; I updated commit sha1. New commits:
99de16f  Changing left_repr > repr so I am consistent.

comment:8 followup: ↓ 9 Changed 4 years ago by
@darij Now both methods use left
and are documented.
What I am suggesting is refactor the multiplication code for the findim algebras into a finite semigroup (well, really finite magma because the product does not have to be associative). Then we would make a findim 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 doublecheck) Days 74, and I would be happy to do some coding sprints with you.
PS  How were the SageGAP days?
comment:9 in reply to: ↑ 8 Changed 4 years ago by
Replying to tscrim:
What I am suggesting is refactor the multiplication code for the findim algebras into a finite semigroup (well, really finite magma because the product does not have to be associative). Then we would make a findim 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 doublecheck) Days 74, and I would be happy to do some coding sprints with you.
Sounds good!
PS  How were the SageGAP 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
 Commit changed from 99de16fca5c2c66b622a358c4de577f165aa7718 to 38529351ae5581559a6a33a6fc6fe825b974ef81
comment:11 followup: ↓ 12 Changed 4 years ago by
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?
 Unexpose
self._module
, since any method that uses linear algebra onself._module
can just as well use it onself
.
 Set
self._module = self
for aTrivialRepresentation
.
 Implement
TrivialRepresentation
using the generalRepresentation
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 leftrightness, and tada you've got a pointless error when you try to add a right representation to the trivial one).
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 4 years ago by
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 ofTrivialRepresentation
, and this is a design question I feel is in need of discussion. What do you think is the right way?
 Unexpose
self._module
, since any method that uses linear algebra onself._module
can just as well use it onself
.
 Set
self._module = self
for aTrivialRepresentation
.
 Implement
TrivialRepresentation
using the generalRepresentation
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 aleft
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 leftrightness, 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 ; followup: ↓ 14 Changed 4 years ago by
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 ofRepresentation
. If you really feel that it should be exposed, then I would havemodule()
returnself
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 twosided). 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*xNo, 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 thinkleft_repr
is more descriptive, and so we should change all of theleft
toleft_repr
. Your thoughts?
I'm fine with left_repr
or with anything, as long as it is the same keyword everywhere.
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 4 years ago by
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 ofRepresentation
. If you really feel that it should be exposed, then I would havemodule()
returnself
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 fromRepresentation
? This I really don't like. Particularly if you don't exposeself._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 treatself._module
as an implementation detail that might not get inherited, but please document this in theinit
sourcecode (just a # comment saying thatself._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 twosided). 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_
ofTrivialRepresentation
, does_from_dict(d)
do the right thing whend == 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 ; followup: ↓ 16 Changed 4 years ago by
Replying to tscrim:
Replying to darij:
Wait, what?
TrivialRepresentation
does not inherit fromRepresentation
? This I really don't like. Particularly if you don't exposeself._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 twosided). 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_
ofTrivialRepresentation
, does_from_dict(d)
do the right thing whend == 0
?This will never happen as
monomial_coefficients
returns adict
. 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 :)
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 4 years ago by
Replying to darij:
Replying to tscrim:
Replying to darij:
Wait, what?
TrivialRepresentation
does not inherit fromRepresentation
? This I really don't like. Particularly if you don't exposeself._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_
ofTrivialRepresentation
, does_from_dict(d)
do the right thing whend == 0
?This will never happen as
monomial_coefficients
returns adict
. 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
withsum(scalar.coefficients())
. If this sum is 0, then it's suddenly adict
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
Replying to tscrim:
Replying to darij:
Replying to tscrim:
Replying to darij:
Wait, what?
TrivialRepresentation
does not inherit fromRepresentation
? This I really don't like. Particularly if you don't exposeself._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
andTrivialRepresentation
will have a common ABC, so I think this issue is moot.
Ah, perfect.
S4. In the
_acted_upon_
ofTrivialRepresentation
, does_from_dict(d)
do the right thing whend == 0
?This will never happen as
monomial_coefficients
returns adict
. 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
withsum(scalar.coefficients())
. If this sum is 0, then it's suddenly adict
full of zeroes.
_from_dict
has an optional argument to check for removing zeros (whose default isTrue
). So this isn't an issue.
Oh! I forgot the semantics of _from_dict
; so it's not as lowlevel as I expected. You are right!
comment:18 Changed 4 years ago by
 Commit changed from 38529351ae5581559a6a33a6fc6fe825b974ef81 to 446f369a6e1bdaaa94e607db4285353e1a7f5438
Branch pushed to git repo; I updated commit sha1. New commits:
9f24c9d  Merge branch 'develop' into public/representations/basic_implementation19613

acab27b  Merge branch 'public/representations/basic_implementation19613' of trac.sagemath.org:sage into public/representations/basic_implementation19613

446f369  Refactoring and adding some documentation as per Darij's comments.

comment:19 Changed 4 years ago by
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 followup: ↓ 22 Changed 4 years ago by
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
 Commit changed from 446f369a6e1bdaaa94e607db4285353e1a7f5438 to 51ae764bac944dcfaf7959000eac6d137ab3f2d4
Branch pushed to git repo; I updated commit sha1. New commits:
51ae764  left_repr > side.

comment:22 in reply to: ↑ 20 Changed 4 years ago by
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
 Commit changed from 51ae764bac944dcfaf7959000eac6d137ab3f2d4 to 3a89f371c3346f1a6528bb8722570412ad1a50cc
Branch pushed to git repo; I updated commit sha1. New commits:
3a89f37  minor doc improvements, 1 bug

comment:24 Changed 4 years ago by
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:
3a89f37  minor doc improvements, 1 bug

New commits:
3a89f37  minor doc improvements, 1 bug

comment:25 Changed 4 years ago by
 Commit changed from 3a89f371c3346f1a6528bb8722570412ad1a50cc to 3e6a1f6f2b5090799cc0763fc54aef05849c357b
Branch pushed to git repo; I updated commit sha1. New commits:
3e6a1f6  Added side to ABC and trivial representation because ABCs need to be completely complete.

comment:26 Changed 4 years ago by
 Commit changed from 3e6a1f6f2b5090799cc0763fc54aef05849c357b to f8b1e3040199be23644dc67c4236018bf6a89b8f
Branch pushed to git repo; I updated commit sha1. New commits:
f8b1e30  One last tweak with the side input.

comment:27 Changed 4 years ago by
 Reviewers set to Darij Grinberg
Thank you! The code now LGTM. Does it LGTY?
comment:28 Changed 4 years ago by
 Status changed from needs_review to positive_review
Yes. Thank you for doing the review.
comment:29 Changed 4 years ago by
Thanks for one of the most useful 500line patches Sage has!
comment:30 Changed 4 years ago by
 Branch changed from public/representations/basic_implementation19613 to f8b1e3040199be23644dc67c4236018bf6a89b8f
 Resolution set to fixed
 Status changed from positive_review to closed
This is a first step to an implementation of group (co)homology.
New commits:
Initial implementation of representations of a semigroup.