17160: categories for finitely generated magmas, semigroups, groups, ...

[Nicolas M. Thiery]

Dear Sage developers,

This e-mail is to request some feedback for:

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

Context
-------

Currently in Sage, any finite semigroup (set with a multiplication) is
automatically assumed to be a finite enumerated set. The enumeration
can be provided explicitly by implementing __iter__. Otherwise, a
default implementation is provided that assumes that a distinguished
set of generators is provided via semigroup_generators.

This was ok so far, but is too restrictive. In particular, with #8678,
Sage often learns indirectly that a given semigroup is actually
finite, and suddenly asks for __iter__ or semigroup_generators to
exist. This is inconvenient, if not just plain impossible to implement
in some extreme cases.

So #17160 is about refining the categories to distinguish the cases
``finite'' and ``finite with generators''. Of course something similar
will need to be done at some point for the other notions of generation
(for additive structures, for additive and multiplicative structures,...).

There has been some discussion on the ticket, which I try to
synthesize here.

Difficulty
----------

There are actually several concepts that we may want to model for a
semigroup M:

(1) The fact that M is finitely generated: we just know that there
exists a finite set of generators for the semigroup. In particular
a finite semigroup is automatically finitely generated.

(2) The fact that M is endowed with a distinguished enumerated set of
generators, provided by a method semigroup_generators. This makes
M into an enumerated set.

(3) The fact that M is endowed with a distinguished finite enumerated
set of generators. This makes M into an enumerated set, but also
allows for defining the Cayley graph, ...

Note that (3) is a subcase of both (1) and (2); however (1) and (2)
together do not imply (3); the distinguished set of generators might
not be one of the finite ones.

Question 1
----------

At this point, implementing all three concepts seems like overkill. I
don't see a practical use case for (1). I'd say (3) is much more
useful than (2), and tend to only implement it for now.

What do you think?

Question 2
----------

(3) is naturally implemented as an axiom to handle that the fact that
a multiplicative structure (M,*) satisfies (3) does not depend on
whether we see `M` as a magma, a semigroup, a monoid, or a
group. There remains to choose a good name for this axiom.

At this point, there are two reasonable candidates; other suggestions
are welcome:

(a) ``with finite set of generators''; variant: ``with finite generating set``
(b) ``finitely generated''


(a) is very explicit; however it's longish and does not read as
nicely, in part because (b) is so much more common in everyday math
discussions:

sage: Semigroups().WithFiniteSetOfGenerators()
Category of semigroups with finite set of generators

sage: Semigroups().FinitelyGenerated()
Category of finitely generated semigroups

On the other hand, with (b), there is a shift between the math concept
and its model in the computer. The latter insists on being
constructive: a finite set of generators must be provided. This may
lead to some of confusion (why isn't a finite semigroup automatically
finitely generated?).

This is not unheard of though. For many other categories there is a
similar distinction between the pure math concept and the more
constructive concept modeled by the category. An object in Semigroups
is not just a set with some product; the product has to be
distinguished and implemented as '__mult__'. Similarly, for an
Euclidean domain, the division method needs to be implemented.

What do you think?

I personally lean toward (b).

Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Volker Braun]

IMHO always assume constructive unless otherwise noted if you do things on the computer. You can pick elements of sets, elements of two sets (or other structure) can actually be distinguished, etc.

Why not have an Iterable() category for everything with __iter__? There is no need to restrict ourselves to the usual pen&paper math nomenclature.

[Nicolas M. Thiery]

Hi!

On Wed, Mar 11, 2015 at 03:22:32PM -0700, Volker Braun wrote:
> IMHO always assume constructive unless otherwise noted if you do
> things on the computer. You can pick elements of sets, elements of
> two sets (or other structure) can actually be distinguished, etc.

> There is no need to restrict ourselves to the usual pen&paper math
> nomenclature.

Thanks Volker for the feedback!

So at this point this leans toward what's in the current
implementation:

- Groups with with a distinguished finite set of generators:

sage: Groups().FinitelyGenerated()
Category of finitely generated groups

in fact a short hand for:

sage: Groups().FinitelyGeneratedAsMagma()
Category of finitely generated groups

- Finite groups with a distinguished finite set of generators (which
is different from just finite groups):

sage: Groups().Finite().FinitelyGenerated()
Category of finite finitely generated groups

- Rings with a distinguished finite set of *multiplicative* generators:

sage: Rings().FinitelyGeneratedAsMagmas()
Category of finitely-generated-as-magma rings

Does this sound acceptable to everyone?

The plan is to finalize this ticket for the Sage days next week, so
quick feedback would be appreciated.

> Why not have an Iterable() category for everything with __iter__?

Yup; in fact we have EnumeratedSets for parents with a distinguished
enumeration (implemented by __iter__ / rank / list)


A few more minor design points:

- All the finite permutation groups implemented in Sage come endowed
with a distinguished set of generators. Do we want the category of
finite permutation groups to be automatically a subcategory of
finite finitely generated permutation groups? This would make the
output a bit shorter:

sage: DihedralGroup(3).category()
Category of finite permutation groups

instead of:

sage: DihedralGroup(3).category()
Category of finite finitely generated permutation groups

- As far as I know, all the finite fields implemented in Sage have
__iter__ implemented. Do we want to keep the category of finite
fields as a subcategory of EnumeratedSets()?

Or maybe a subcategory Monoids().FinitelyGenerated()? In this case,
we would need to provide multiplicative generators. Is there an easy
way to implement this generically for any finite field?