Finitely generated axiom for (mutiplicative) magmas, semigroups, monoids, groups

[nthiery]

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

Depends on #10668
Depends on #15852

CC: @tscrim @sagetrac-sage-combinat @darijgr @avirmaux

Component: categories

Keywords: days64

Author: Nicolas M. Thiéry

Branch/Commit: 19ceb81

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:1

Also be good for rings and algebras.

[nthiery]

comment:3

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

[nthiery]

Author: Nicolas M. Thiéry

[nthiery]

Branch: u/nthiery/categories/finitely-generated-magmas-17160

[tscrim]

comment:6

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/morphism-methods-10668'
f027ce2	17610: first draft of finitely generated axiom for magmas/groups/axioms

[tscrim]

Commit: f027ce2

[nthiery]

comment:7

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

[nthiery]

comment:8

The dependency on #10668 is mostly for convenience: #10668 fixes the doctests in c3_controlled to not need to be updated everytime the category hierarchy changes.

[nthiery]

Dependencies: #10668

[tscrim]

comment:9

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.

[nthiery]

comment:10

Replying to @tscrim:

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.

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

[tscrim]

comment:11

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 for WithGeneratingSet, 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?

[nthiery]

comment:12

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 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.

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 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.

Well, also all the code to build the Cayley graph, to compute
J/R/L-classes, 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 sage-dev. As usual this
takes a bit of preparation to have an efficient discussion there.
I'll try to do this soon.

Cheers,
Nicolas

[tscrim]

comment:13

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 non-enumerated 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/L-classes, 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 sage-dev. As usual this
takes a bit of preparation to have an efficient discussion there.
I'll try to do this soon.

Probably.

[sagetrac-git]

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

dabcafd

Merge branch 'develop' into t/17160/categories/finitely-generated-magmas-17160

[sagetrac-git]

Changed commit from f027ce2 to dabcafd

[nthiery]

comment:15

Replying to @nthiery:

We probably should bring the discussion to sage-dev.

Done: https://groups.google.com/d/msg/sage-devel/1du_5IhxsUU/j4hr75fBb9IJ

[sagetrac-git]

Changed commit from dabcafd to cf9b429

[sagetrac-git]

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

cf9b429

Fixed ReST typo

[sagetrac-git]

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

aff2689	17160: fixed category for finite set endomaps + minor `__init__` refactoring
4b3d74c	Merge branch 'develop' into categories/finitely-generated-magmas-17160

[sagetrac-git]

Changed commit from cf9b429 to 4b3d74c

[sagetrac-git]

Changed commit from 4b3d74c to ad5d6c0

[sagetrac-git]

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

ad5d6c0

8678: permutation groups are finitely generated, finite fields are enumerated, fixes

[nthiery]

comment:24

This ticket does not really depend on #17160, but the build tends to fail without it, so I merged it in.

[tscrim]

comment:25

LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed keywords from none to days64

[sagetrac-git]

Changed commit from ef01ef0 to 975c008

[sagetrac-git]

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/finitely-generated-magmas-17160
975c008	Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into categories/finitely-generated-magmas-17160

[tscrim]

comment:28

Simple merge.

[vbraun]

comment:29

conflicts with #15852

[tscrim]

Changed branch from u/nthiery/categories/finitely-generated-magmas-17160 to public/categories/finitely_generated_magma-17160

[tscrim]

Changed commit from 975c008 to 19ceb81

[tscrim]

comment:30

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_magma-17160
19ceb81	Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160

[tscrim]

Changed dependencies from #10668 to #10668 #15852

[vbraun]

Changed branch from public/categories/finitely_generated_magma-17160 to 19ceb81