Opened 5 years ago
Closed 5 years ago
#17160 closed enhancement (fixed)
Finitely generated axiom for (mutiplicative) magmas, semigroups, monoids, groups
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  categories  Keywords:  days64 
Cc:  tscrim, sagecombinat, darij, virmaux  Merged in:  
Authors:  Nicolas M. Thiéry  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  19ceb81 (Commits)  Commit:  19ceb8124d27ba0124fb08a232c05924bb7114b0 
Dependencies:  #10668 #15852  Stopgaps: 
Description (last modified by )
This introduce an axiom FinitelyGeneratedAsMagma?, as well as related categories with axioms for magmas, semigroups and groups::
sage: Groups().FinitelyGeneratedAsMagma() Category of finitely generated groups
For ease of notations, when there is no ambiguity, one can do::
sage: Groups().FinitelyGenerated() Category of finitely generated groups
One motivation for this change (for #8678) is that finite semigroups
in Sage used to be automatically endowed with an EnumeratedSets
structure; the default enumeration is then obtained by iteratively
multiplying the semigroup generators. This forced any finite semigroup
to either implement an enumeration, or provide semigroup generators;
this was often inconvenient.
Instead, finite semigroups that provide a distinguished finite set of
generators with semigroup_generators
should now explicitly declare
themselves in the category of FinitelyGeneratedSemigroups
:
sage: Semigroups().FinitelyGenerated() Category of finitely generated semigroups
This is a backward incompatible change.
TODO:
 Use the occasion to migrate TransitiveIdeal? to RecursivelyEnumeratedSet?
Change History (31)
comment:1 followup: ↓ 3 Changed 5 years ago by
 Cc tscrim added
 Component changed from PLEASE CHANGE to categories
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 5 years ago by
 Description modified (diff)
comment:3 in reply to: ↑ 1 Changed 5 years ago by
Replying to tscrim:
Also be good for rings and algebras.
Yes, and additive magmas as well. And possibly crystals, ... But I'll leave those to a later ticket. And for modules, we alreay have FiniteDimensional
.
Cheers,
Nicolas
comment:4 Changed 5 years ago by
 Cc sagecombinat darij virmaux added
 Description modified (diff)
comment:5 Changed 5 years ago by
 Branch set to u/nthiery/categories/finitelygeneratedmagmas17160
comment:6 followup: ↓ 7 Changed 5 years ago by
 Commit set to f027ce2b5e1abe22d49bcdc96f2cfeebced8fc16
I know this isn't set for review yet, but just to note that a finite magma is automatically finitely generated. So I think we should have this reflected in the category structure; in particular, so we don't have lines like this:
Parent.__init__(self, category = Semigroups().Finite().FinitelyGenerated())
If you need someone to review it, just let me know when this is ready.
Last 10 new commits:
d5d3a97  10668: improved description of the HomsetsOf class

5416ba0  Add a note on the MRO used for Homset._abstract_element_class

23639a9  Fix more typos

02a6a8a  10668: fixed representation of the category of endsets

477d381  10668: Homsets.Endset.super_category > extra_super_category + documentation

877bfdb  10668: fix: Modules.EndCategory > Modules.Homsets.Endset + made it functional: endsets of modules are algebras

f86824e  10668: documentation for HomsetsCategory.category_of + fixed typo in doctest nearby

787f461  10668: proofreading of Homsets.category_of

5f96686  17160: Merge branch 'categories/morphismmethods10668'

f027ce2  17610: first draft of finitely generated axiom for magmas/groups/axioms

comment:7 in reply to: ↑ 6 Changed 5 years ago by
Replying to tscrim:
I know this isn't set for review yet,
Thanks for having looked at it!
but just to note that a finite magma is automatically finitely generated. So I think we should have this reflected in the category structure; in particular, so we don't have lines like this:
Parent.__init__(self, category = Semigroups().Finite().FinitelyGenerated())
As stated in the description, the point of the ticket is precisely to make a distinction between finite magmas (which are indeed finitely generated by definition), and finite monoids that are explicitly endowed with a finite set of generators. The new axiom is about the latter. So, above, we anyway want something like:
Semigroups().Finite().XXX()
Granted, the current name of the axiom is misleading, and I am hesitant about it. I also considered:
sage: Groups().Finite().WithFiniteSetOfGenerators?() Category of groups with finite set of generators
It's very explicit but feels like heavy notation; and it does not feel as appealing as "finitely generated" which immediately rings a bell in a mathematician's head. Also, it seems to me that being "finitely generated" is rather useless computationally speaking if no finite set of generators is provided; so we would not be using that nice name for a weaker purpose anyway.
I guess that's the main design decision to be taken in this ticket. The rest is rather straightforward.
Ah, yes, the other design decision is whether it's acceptable to break backward compatibility. I'll be the first one to be hurt by this change, and I believe it's worth it ...
Opinions anyone?
If you need someone to review it, just let me know when this is ready.
Ok, thanks! Darij would be a good candidate to give feedback too!
Cheers,
Nicolas
comment:8 Changed 5 years ago by
 Dependencies set to #10668
comment:9 followup: ↓ 10 Changed 5 years ago by
Saying this ticket is for a specified fixed set of generators contracts this statement:
And for modules, we alreay have
FiniteDimensional
.
I think we should make an analogy to WithBasis
and FiniteDimensional
by having 2 axioms, WithGeneratingSet
and FinitelyGenerated
. This would give FinitelyGenerated
a purpose, would still allow the current goal of not having to specify the enumeration, and allow the option for infinitely generated objects.
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 5 years ago by
Replying to tscrim:
I think we should make an analogy to
WithBasis
andFiniteDimensional
by having 2 axioms,WithGeneratingSet
andFinitelyGenerated
. This would giveFinitelyGenerated
a purpose, would still allow the current goal of not having to specify the enumeration, and allow the option for infinitely generated objects.
I considered this and I agree that this would have the advantage of
being consistent with the basis things. However I don't see what I
would put in the categories with axiom for FinitelyGenerated
axiom
besides the subcategories with axioms for WithGeneratingSet
, so this
looks like overkill. Besides,
Categories of finitely generated group with generating set
is not great. I am torn.
Opinions anyone else?
Cheers,
Nicolas
comment:11 in reply to: ↑ 10 ; followup: ↓ 12 Changed 5 years ago by
Replying to nthiery:
I considered this and I agree that this would have the advantage of being consistent with the basis things. However I don't see what I would put in the categories with axiom for
FinitelyGenerated
axiom besides the subcategories with axioms forWithGeneratingSet
, so this looks like overkill. Besides,Categories of finitely generated group with generating set
is not great. I am torn.
I have things that have infinite (enumerable) distinguished generating sets (ex. free group/monoid with generators indexed by NN
or Yangians #15484), so separating these axioms will be useful. In fact, the enumeration could be done in for the general WithGeneratingSet
category and would (at least should) error out if the generating set is not enumerable. Although I only know of 1 thing which will be finite dimensional but doesn't come with a distinguished basis. Plus I think we could do an extra case in _repr_object_names_static
to change the repr into:
Category of groups with finite generating set
Here's another thought, what about we look at the cardinality of the generating set? So we only have WithGeneratingSet
which calls is_finitely_generated
, whose default is to look at the cardinality of the generating set to determine the output of repr. At least that's the only place where I could see us (currently) using the fact that the generating set is finite. For the enumeration, all we really need is the generating set is enumerable. Although I guess we really want to add EnumeratedSets
to the category heirachy, so this probably is not so useful of an idea...
Opinions anyone else?
Darij, Aladin, or anyone else, your thoughts?
comment:12 in reply to: ↑ 11 ; followups: ↓ 13 ↓ 15 Changed 5 years ago by
Replying to tscrim:
I have things that have infinite (enumerable) distinguished generating sets (ex. free group/monoid with generators indexed by
NN
or Yangians #15484), so separating these axioms will be useful. In fact, the enumeration could be done in for the generalWithGeneratingSet
category and would (at least should) error out if the generating set is not enumerable. Although I only know of 1 thing which will be finite dimensional but doesn't come with a distinguished basis.
Another issue: having a distinguished set of generators and being finitely generated does not necessarily imply that the distinguished set of generators is finite. So we would actually need three axioms: "WithGenerators?", "FinitelyGenerated?", and "WithFiniteGeneratingSet?". So for a finite magma we still would need to do "Magmas().Finite().WithFiniteGeneratingSet?()".
I am not sure this is worth the complication. Especially since we will have to do something similar for additive magmas, rings, fields, ...
Plus I think we could do an extra case in
_repr_object_names_static
to change the repr into:Category of groups with finite generating set
That should be easy indeed.
Here's another thought, what about we look at the cardinality of the generating set? So we only have
WithGeneratingSet
which callsis_finitely_generated
, whose default is to look at the cardinality of the generating set to determine the output of repr. At least that's the only place where I could see us (currently) using the fact that the generating set is finite.
Well, also all the code to build the Cayley graph, to compute J/R/Lclasses, etc. In short all my finite semigroups code :)
I oppose querying the cardinality, or even just is_finite, for this can be super expensive if not undecidable. We really want something declarative here.
Darij, Aladin, or anyone else, your thoughts?
Yup?
We probably should bring the discussion to sagedev. As usual this takes a bit of preparation to have an efficient discussion there. I'll try to do this soon.
Cheers,
Nicolas
comment:13 in reply to: ↑ 12 Changed 5 years ago by
Replying to nthiery:
Another issue: having a distinguished set of generators and being finitely generated does not necessarily imply that the distinguished set of generators is finite. So we would actually need three axioms: "WithGenerators?", "FinitelyGenerated?", and "WithFiniteGeneratingSet?". So for a finite magma we still would need to do "Magmas().Finite().WithFiniteGeneratingSet?()".
I am not sure this is worth the complication. Especially since we will have to do something similar for additive magmas, rings, fields, ...
...Right... Although I think the right thing is actually WithEnumeratedGeneratingSet
as we can do the same thing for infinite enumerated generating sets. However this is mostly an empty category/axiom because we can write generic code for WithGeneratingSet
which will error out (at the right spot) for nonenumerated generating sets. In many ways, it's just a join with EnumeratedSets
.
Another thought, we have 2 axioms FinitelyGenerated
and WithGenerators
and we create new join categories such as SemigroupWithEnumeratedGeneratingSet
which implements an __iter__
which calls semigroup_generators
. The reasoning would be for monoids, we'd want to monoid_generators
and need a separate method to avoid ambiguities similar to #15381. Or would we use gens
in this case and just push everything up to the category?
For rings, algebras, fields, I think we get this for free from the axiom magic and that they are subcategories of Magma
. Perhaps I'm misunderstanding how things work?
Well, also all the code to build the Cayley graph, to compute J/R/Lclasses, etc. In short all my finite semigroups code :)
I oppose querying the cardinality, or even just is_finite, for this can be super expensive if not undecidable. We really want something declarative here.
Yep, it's a bad idea.
We probably should bring the discussion to sagedev. As usual this takes a bit of preparation to have an efficient discussion there. I'll try to do this soon.
Probably.
comment:14 Changed 5 years ago by
 Commit changed from f027ce2b5e1abe22d49bcdc96f2cfeebced8fc16 to dabcafd7bb9100fbe325578e5f4a8252b50c90a4
Branch pushed to git repo; I updated commit sha1. New commits:
dabcafd  Merge branch 'develop' into t/17160/categories/finitelygeneratedmagmas17160

comment:15 in reply to: ↑ 12 Changed 5 years ago by
Replying to nthiery:
We probably should bring the discussion to sagedev.
Done: https://groups.google.com/d/msg/sagedevel/1du_5IhxsUU/j4hr75fBb9IJ
comment:16 Changed 5 years ago by
 Commit changed from dabcafd7bb9100fbe325578e5f4a8252b50c90a4 to cf9b429455e3330ff76d544bf39bc9ff7c76e514
Branch pushed to git repo; I updated commit sha1. New commits:
cf9b429  Fixed ReST typo

comment:17 Changed 5 years ago by
 Commit changed from cf9b429455e3330ff76d544bf39bc9ff7c76e514 to 4b3d74c41cfec35c35ab2262d6dc17dd90ef3472
comment:18 Changed 5 years ago by
 Description modified (diff)
comment:19 Changed 5 years ago by
 Commit changed from 4b3d74c41cfec35c35ab2262d6dc17dd90ef3472 to ad5d6c0dc9cf55eed4900ed76df26f4a3e86f73f
Branch pushed to git repo; I updated commit sha1. New commits:
ad5d6c0  8678: permutation groups are finitely generated, finite fields are enumerated, fixes

comment:20 Changed 5 years ago by
 Commit changed from ad5d6c0dc9cf55eed4900ed76df26f4a3e86f73f to 839200e376b595f7bfe3247c55fc31adf0693ef3
Branch pushed to git repo; I updated commit sha1. New commits:
839200e  8678: More doctest updates. Should almost pass all tests.

comment:21 Changed 5 years ago by
 Status changed from new to needs_review
comment:22 Changed 5 years ago by
 Commit changed from 839200e376b595f7bfe3247c55fc31adf0693ef3 to 919a215d94e8e14eb75818021fa3af38831daf5e
Branch pushed to git repo; I updated commit sha1. New commits:
919a215  Merge branch 'develop = sage 6.6 beta6' into categories/finitelygeneratedmagmas17160

comment:23 Changed 5 years ago by
 Commit changed from 919a215d94e8e14eb75818021fa3af38831daf5e to ef01ef0288027084170f033b8cb8b46fa2d47be6
comment:24 Changed 5 years ago by
This ticket does not really depend on #17160, but the build tends to fail without it, so I merged it in.
comment:25 Changed 5 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM.
comment:26 Changed 5 years ago by
 Keywords days64 added
 Milestone changed from sage6.4 to sage6.6
comment:27 Changed 5 years ago by
 Commit changed from ef01ef0288027084170f033b8cb8b46fa2d47be6 to 975c008ade2bc70319c286d9eb09eacdc75cafed
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
7488127  Merge branch 'develop=6.6rc2' into categories/finitelygeneratedmagmas17160

975c008  Merge branch 'u/nthiery/categories/finitelygeneratedmagmas17160' of trac.sagemath.org:sage into categories/finitelygeneratedmagmas17160

comment:29 Changed 5 years ago by
 Status changed from positive_review to needs_work
conflicts with #15852
comment:30 Changed 5 years ago by
 Branch changed from u/nthiery/categories/finitelygeneratedmagmas17160 to public/categories/finitely_generated_magma17160
 Commit changed from 975c008ade2bc70319c286d9eb09eacdc75cafed to 19ceb8124d27ba0124fb08a232c05924bb7114b0
 Dependencies changed from #10668 to #10668 #15852
 Status changed from needs_work to positive_review
Trivial rebase.
New commits:
dbadd6a  15852: uncouple Sequence from categories

1f9c338  Merge branch 'develop' into t/15852/15852

6b12bda  Merge branch 'u/rws/15852' of trac.sagemath.org:sage into public/categories/finitely_generated_magma17160

19ceb81  Merge branch 'u/nthiery/categories/finitelygeneratedmagmas17160' of trac.sagemath.org:sage into public/categories/finitely_generated_magma17160

comment:31 Changed 5 years ago by
 Branch changed from public/categories/finitely_generated_magma17160 to 19ceb8124d27ba0124fb08a232c05924bb7114b0
 Resolution set to fixed
 Status changed from positive_review to closed
Also be good for rings and algebras.