Opened 5 years ago

Closed 4 years ago

#17160 closed enhancement (fixed)

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

Reported by: nthiery Owned by:
Priority: major Milestone: sage-6.6
Component: categories Keywords: days64
Cc: tscrim, sage-combinat, 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 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:

Change History (31)

comment:1 follow-up: Changed 5 years ago by tscrim

  • Cc tscrim added
  • Component changed from PLEASE CHANGE to categories
  • Type changed from PLEASE CHANGE to enhancement

Also be good for rings and algebras.

comment:2 Changed 5 years ago by nthiery

  • Description modified (diff)

comment:3 in reply to: ↑ 1 Changed 5 years ago by nthiery

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

Last edited 5 years ago by nthiery (previous) (diff)

comment:4 Changed 5 years ago by nthiery

  • Authors set to Nicolas M. Thiéry
  • Cc sage-combinat darij virmaux added
  • Description modified (diff)

comment:5 Changed 5 years ago by nthiery

  • Branch set to u/nthiery/categories/finitely-generated-magmas-17160

comment:6 follow-up: Changed 5 years ago by tscrim

  • 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:

d5d3a9710668: improved description of the HomsetsOf class
5416ba0Add a note on the MRO used for Homset._abstract_element_class
23639a9Fix more typos
02a6a8a10668: fixed representation of the category of endsets
477d38110668: Homsets.Endset.super_category -> extra_super_category + documentation
877bfdb10668: fix: Modules.EndCategory -> Modules.Homsets.Endset + made it functional: endsets of modules are algebras
f86824e10668: documentation for HomsetsCategory.category_of + fixed typo in doctest nearby
787f46110668: proofreading of Homsets.category_of
5f9668617160: Merge branch 'categories/morphism-methods-10668'
f027ce217610: first draft of finitely generated axiom for magmas/groups/axioms

comment:7 in reply to: ↑ 6 Changed 5 years ago by nthiery

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 nthiery

  • Dependencies set to #10668

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.

comment:9 follow-up: Changed 5 years ago by tscrim

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 ; follow-up: Changed 5 years ago by nthiery

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

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

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?

comment:12 in reply to: ↑ 11 ; follow-ups: Changed 5 years ago by nthiery

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

comment:13 in reply to: ↑ 12 Changed 5 years ago by tscrim

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.

comment:14 Changed 5 years ago by git

  • Commit changed from f027ce2b5e1abe22d49bcdc96f2cfeebced8fc16 to dabcafd7bb9100fbe325578e5f4a8252b50c90a4

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

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

comment:15 in reply to: ↑ 12 Changed 5 years ago by nthiery

Replying to nthiery:

We probably should bring the discussion to sage-dev.

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

comment:16 Changed 5 years ago by git

  • Commit changed from dabcafd7bb9100fbe325578e5f4a8252b50c90a4 to cf9b429455e3330ff76d544bf39bc9ff7c76e514

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

cf9b429Fixed ReST typo

comment:17 Changed 5 years ago by git

  • Commit changed from cf9b429455e3330ff76d544bf39bc9ff7c76e514 to 4b3d74c41cfec35c35ab2262d6dc17dd90ef3472

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

aff268917160: fixed category for finite set endomaps + minor __init__ refactoring
4b3d74cMerge branch 'develop' into categories/finitely-generated-magmas-17160

comment:18 Changed 5 years ago by nthiery

  • Description modified (diff)

comment:19 Changed 5 years ago by git

  • Commit changed from 4b3d74c41cfec35c35ab2262d6dc17dd90ef3472 to ad5d6c0dc9cf55eed4900ed76df26f4a3e86f73f

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

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

comment:20 Changed 5 years ago by git

  • Commit changed from ad5d6c0dc9cf55eed4900ed76df26f4a3e86f73f to 839200e376b595f7bfe3247c55fc31adf0693ef3

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

839200e8678: More doctest updates. Should almost pass all tests.

comment:21 Changed 5 years ago by nthiery

  • Status changed from new to needs_review

comment:22 Changed 5 years ago by git

  • Commit changed from 839200e376b595f7bfe3247c55fc31adf0693ef3 to 919a215d94e8e14eb75818021fa3af38831daf5e

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

919a215Merge branch 'develop = sage 6.6 beta6' into categories/finitely-generated-magmas-17160

comment:23 Changed 5 years ago by git

  • Commit changed from 919a215d94e8e14eb75818021fa3af38831daf5e to ef01ef0288027084170f033b8cb8b46fa2d47be6

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

5e6c707Do not build the Jinja2 docs
ef01ef0Merge branch 't/18012/sphinx_depends_on_jinja2' into categories/finitely-generated-magmas-17160

comment:24 Changed 5 years ago by nthiery

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 tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:26 Changed 5 years ago by tscrim

  • Keywords days64 added
  • Milestone changed from sage-6.4 to sage-6.6

comment:27 Changed 4 years ago by git

  • 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:

7488127Merge branch 'develop=6.6rc2' into categories/finitely-generated-magmas-17160
975c008Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into categories/finitely-generated-magmas-17160

comment:28 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

Simple merge.

comment:29 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

conflicts with #15852

comment:30 Changed 4 years ago by tscrim

  • Branch changed from u/nthiery/categories/finitely-generated-magmas-17160 to public/categories/finitely_generated_magma-17160
  • 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:

dbadd6a15852: uncouple Sequence from categories
1f9c338Merge branch 'develop' into t/15852/15852
6b12bdaMerge branch 'u/rws/15852' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160
19ceb81Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160

comment:31 Changed 4 years ago by vbraun

  • Branch changed from public/categories/finitely_generated_magma-17160 to 19ceb8124d27ba0124fb08a232c05924bb7114b0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.