Classes of combinatorial structures

[sagetrac-elixyre]

I propose several feature in this ticket:

• some generic methods for all combinatorial structures:

  • from a structure: a method "grade" to compute the degree of the structure
  • from a graded component: a method "ambient" to find the class of all structures
    I put those methods in a category called ClassesOfCombinatorialStructure.

• a generic pattern to define a class of combinatorial structure

• a fix of some combinatorial structure to be coherent with that... (permutations, compositions, binarytrees).

CC: @nthiery @zabrocki @alauve @kevindilks

Component: combinatorics

Author: Jean-Baptiste Priez

Branch/Commit: u/elixyre/class_of_combinatorial_structures @ 2e03999

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

[sagetrac-elixyre]

comment:1

So... I want push the code but... it is ask the "git@trac... password:". (It is a strange problem, from an other folder of sage I have not this fu**** problem)

[sagetrac-elixyre]

Branch: u/elixyre/class_of_combinatorial_structures

[nathanncohen]

Commit: 75a10e9

[nathanncohen]

New commits:

75a10e9

Ticket classes of combinatorial structures

[kcrisman]

comment:4

I have no real interest in this, but I'm curious as to whether such a long name needs to be in the global namespace. We already have way too many categories there that are fairly "empty" when you try to use them directly (as opposed to giving properties to actual mathematical objects).

[sagetrac-git]

Changed commit from 75a10e9 to c0e3c31

[sagetrac-git]

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

c0e3c31

ticket 17367: update documentation

[sagetrac-elixyre]

comment:6

Hey,

Sorry I'm the king of duplicate... Plus #16465 it is my own ticket...

[sagetrac-git]

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

5a300c7

Merge branch 'u/elixyre/class_of_combinatorial_structures' of git://trac.sagemath.org/sage into t17367/class_of_comb_struct

[sagetrac-git]

Changed commit from c0e3c31 to 5a300c7

[sagetrac-git]

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

6771a33

ticket 17367: fix the categories of permutations

[sagetrac-git]

Changed commit from 5a300c7 to 6771a33

[sagetrac-elixyre]

comment:9

Ok... this is not really a duplicate... #16465 contains lot of things... to many... I'm not sure about its destiny! whatever...

This ticket #17367 provides a category of combinatorial classes sage.categories.classes_of_combinatorial_structures.py.
It contains some methods that I need to define a simple design of (combinatorial) Hopf algebras.

For example, most of the time we define graded connected Hopf algebras indexed by a "connected" class of combinatorial structure C. This means the unit and the counit MUST be automatically defined by the unique element of the graded component of degree 0 of C (As an user, I don't want write again and again this same code).

• Problem: In sage, there is no way to ask C.graded_component(n).

This ticket provides to that, it provides those kind of methods. It also provides some code to easily design a class of combinatorial structures (sage.combinat.structures.__init__.py)

new files:

• sage.categories.classes_of_combinatorial_structures.py (the category)
• sage.categories.examples.classes_of_combinatorial_structures.py (an example)
• sage.combinat.structures.__init__.py (the design used in the example)

all classes of combinatorial structures modified to use the category:

• sage.combinat.composition.py
• sage.combinat.permutation.py
• sage.combinat.binary_trees.py

[zabrocki]

comment:10

I am talking with Jean-Baptiste so I want to make a few things clear in this ticket for the record. My main question when I look at this category, is how is it different than InfiniteEnumeratedSet? and his answer is that an infinite enumerated set is not necessarily graded while this is the main point of defining this category.

Follow-up question is then is/should/could ClassesOfCombinatorialStructure be a sub-category of GradedSet and InfiniteEnumeratedSet? He answers: it could be.

Follow-up question is then a better name InfiniteGradedSet? Answer: why not?

The reason graded infinite enumerated sets are ALL over combinat and we need common methods to work with them and create combinatorial Hopf algebras of a ClassesOfCombinatorialStructure. Aaron Lauve was asking me precisely about this structure last time I spoke with him in person (hence I add him to the cc list). The idea is to create category for defining any combinatorial class for which once the basics of the class are defined then one can make "the combinatorial Hopf algebra" of that class.

[zabrocki]

comment:11

Jean-Baptiste is proposing giving the Compositions, Permutations and BinaryTrees this treatment (as they are some of the first objects that will be used to create a CHA). I propose adding SetPartitions to that list since NCSym is already defined and should follow that structure.

[zabrocki]

comment:12

But we noticed that it is not necessarily the cases that this category is a sub-category of InfiniteEnumeratedSet, instead it could be the set is finite but for all n>some fixed N, the graded component is empty. Hence this is a subcategory of SetsWithGrading and EnumeratedSets and its name might be EnumeratedSetsWithGrading.

[alauve]

comment:13

Great ideas. (I prefer to keep "combinatorial' out of the name, if possible.)

For the record, we're talking about enumeratable sets, right?

Set partitions, etc., may be enumeratable, but I don't want to specify an enumeration (i.e., make it into an enumerated set) if I don't have to.... Or maybe I should?
(This would certainly be necessary if I planned to identify bases of homogeneous graded slices of a Hopf algebra with QQⁿ for some n, but aside from that, I don't know that I'd want to specify an enumeration.)

[zabrocki]

comment:14

In this category you would need to specify the enumeration and it is graded (by non-negative integers by default).
For each n one would specify a FiniteEnumeratedSet which is iterable. Are you thinking of structures that are not captured by this definition?

[sagetrac-git]

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

d7831e3

ticket 17367: fix the notation ClassOfCombinatorialStructures becomes EnumeratedSetsWithGrading and define set_partition in this category

[sagetrac-git]

Changed commit from 6771a33 to d7831e3

[sagetrac-git]

Changed commit from d7831e3 to c13301a

[sagetrac-git]

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

c13301a

ticket 17367: change some notations: Structure becomes ElementStructure and StructuresClass becomes ParentStructure

[videlec]

comment:17

Hello,

I strongly think that creating this category is useless and I certainly understand that it is needed. What I propose is to not create a new category but make this featured sets with NN grading and finite slices available. What I would rather implement is:

• making the grading set a parameter of the category SetsWithGrading (in your case it would be NN)
• adding an axiom FiniteSlice to SetsWithGrading
  That way, what you are trying to define would simply be

sage: SetsWithGrading(NN).FiniteSlices() & EnumeratedSets()
Join of Category of sets with grading Non negative integer semiring with finite slices
    and Category of enumerated sets

(.. the names are awful, but I hope that the plan is clear ...).

Related to my previous remark, you add plenty of stuff that should be discussed at the level of SetsWithGrading. For example the presence of a .grade() method. And that was actually already discussed while working on #10193 (but sadly not written explicitely in the ticket): we want Sage to support structure of objects that do not care such much about their environment (i.e. facade sets). A good example is

sage: F = FiniteEnumeratedSet([1,2,3])
sage: F.an_element().parent()
Integer Ring

Some terminology and english weirdnesses:

• What is denumerable?

• Where did you found your definition of structure? combinatorial structure would make more sense. I do not understand comment:13. If you talk about structure to a random mathematician, it will rarely end up with some combinatorics in mind.

Vincent

[zabrocki]

comment:18

If same thing can be achieved by adding to SetsWithGrading, that would be great, but I imagine that some thought will have to go into the applications of this category to make sure they can still be as simple (since one goal is to make it easy to define a combinatorial Hopf algebra, +others).

I didn't know the word denumerable either but in my dictionary it says "adjective - Mathematics - able to be counted by a one-to-one correspondence with the infinite set of integers" so I figure that is about right.

Jean-Baptiste and I had a discussion about the use of structure and he was taking it from the use in species and from sage.misc.structure. I agree that it seems a bit too vague a word which prompted the switch to ElementStructure and ParentStructure. Maybe this requires further thought.

[sagetrac-elixyre]

comment:19

Hi Vincent,

Thank you about your comments.

Replying to @videlec:

I strongly think that creating this category is useless

This seems not totally useless to create a new category or I don't know how to do that easily using the category framework of sage.
Let me ask you how to that in the following...

and I certainly understand that it is needed. What I propose is to not create a new category but make this featured sets with NN grading and finite slices available. What I would rather implement is:

• making the grading set a parameter of the category SetsWithGrading (in your case it would be NN)

The parameter grading set is already provided in the SetsWithGrading category.

• adding an axiom FiniteSlice to SetsWithGrading

I also wish to provide a category GradedComponent (or Subset) with methods ambient (which return the set with grading) and grade (why not). Where put this class:

class SetsWithGrading(Category):
   ....
   class GradedComponent(Category):
      def super_category(self):
         return .???.
      class ParentMethods:
         def ambient(self):
            pass
         def grade(self):
            pass

It seems natural to have GradedComponent as a nested class of SetWithGrading, right? (There is no reason that it appears elsewhere.)

At this point, if I use FiniteSlice as an axiom, a priori this class GradedComponent should have FiniteSets (or better FiniteEnumeratedSets) as super category but without the axiom this only should have Sets. How do that (easily and properly)?

So my opinion is FiniteSlice is not an axiom and the code of GradedComponent should be duplicate, one using Sets as super category and the other using FiniteSets.

That way, what you are trying to define would simply be

sage: SetsWithGrading(NN).FiniteSlices() & EnumeratedSets()
Join of Category of sets with grading Non negative integer semiring with finite slices
    and Category of enumerated sets

(.. the names are awful, but I hope that the plan is clear ...).

If we have a finite sets (in sage), could we assume that it is an enumerated sets? (I suppose the answer is no but...)

[videlec]

comment:20

Replying to @sagetrac-elixyre:

Replying to @videlec:

I strongly think that creating this category is useless

This seems not totally useless to create a new category or I don't know how to do that easily using the category framework of sage.
Let me ask you how to that in the following...

and I certainly understand that it is needed. What I propose is to not create a new category but make this featured sets with NN grading and finite slices available. What I would rather implement is:

• making the grading set a parameter of the category SetsWithGrading (in your case it would be NN)

The parameter grading set is already provided in the SetsWithGrading category.

This is not true. It is provided by the parents that belong to the category. You have no category Sets with grading NN. Whereas you have

sage: Modules(ZZ)
Category of modules over Integer Ring
sage: Modules(Zmod(4)['a','b'])
Category of modules over Multivariate Polynomial Ring
  in a, b over Ring of integers modulo 4

In the case of SetsWithGrading the grading set is not attached to the category. It is just a mandatory attribute (in the common sense) of the parents of this category.

• adding an axiom FiniteSlice to SetsWithGrading

I also wish to provide a category GradedComponent (or Subset) with methods ambient (which return the set with grading) and grade (why not). Where put this class:

Do you mean a method of the parent belonging to that category?

• For the .ambient() method, this is not specific to the parent that are the graded component of a graded set. The lack is that there is nothing right now for a parent that needs to be seen as a subset of another parent. That would be the most natural. The facades are already close to that.

• Do you really want to impose a .grade() method in each of the graded component?

• On the other hand, I think that there should be a special mechanism in SetsWithGrading to be able to specify any restriction on the category of the graded components. That would be the most natural and certainly the easiest to implement.

It seems natural to have GradedComponent as a nested class of SetWithGrading, right? (There is no reason that it appears elsewhere.)

I don't think that this GradedComponent should exist. As I said above, it would be better to have something to be able to specify an ambient parent.

At this point, if I use FiniteSlice as an axiom, a priori this class GradedComponent should have FiniteSets (or better FiniteEnumeratedSets) as super category but without the axiom this only should have Sets. How do that (easily and properly)?

I still do not think that this GradedComponent should exist... so there is no trouble.

So my opinion is FiniteSlice is not an axiom and the code of GradedComponent should be duplicate, one using Sets as super category and the other using FiniteSets.

Certainly not. Solutions for categories should never be with a class for each particular problem.

If we have a finite sets (in sage), could we assume that it is an enumerated sets? (I suppose the answer is no but...)

Indeed. The problem is that the behavior are actually quite different (see also #18411 comment 39 and #18411 comment 40):

sage: FiniteEnumeratedSet([1,2,3]) == FiniteEnumeratedSet([3,2,1])
False
sage: Set([1,2,3]) == Set([3,2,1])
True

Enumerated in the Sage category context does not mean iterable, it is rather with a presribed iteration order. Nicolas wanted a new category IterableSets but I think it is going too far.

When we will converge to something reasonable, it would be better to split the features:

• a ticket to implement being subset of a parent (i.e. the ambient method)
• a ticket to implement the category restrictions on the slices
• etc

The most important is to actually not focus on your particular case if you want to implement something useful for categories.

[sagetrac-elixyre]

comment:21

Replying to @videlec:

This is not true. It is provided by the parents that belong to the category. You have no category Sets with grading NN. Whereas you have

sage: Modules(ZZ)
Category of modules over Integer Ring
sage: Modules(Zmod(4)['a','b'])
Category of modules over Multivariate Polynomial Ring
  in a, b over Ring of integers modulo 4

In the case of SetsWithGrading the grading set is not attached to the category. It is just a mandatory attribute (in the common sense) of the parents of this category.

I understand your point. What I say that it is already a method which provides to the parent a default grading set: .grading_set().

• adding an axiom FiniteSlice to SetsWithGrading

I also wish to provide a category GradedComponent (or Subset) with methods ambient (which return the set with grading) and grade (why not). Where put this class:

Do you mean a method of the parent belonging to that category?

• For the .ambient() method, this is not specific to the parent that are the graded component of a graded set. The lack is that there is nothing right now for a parent that needs to be seen as a subset of another parent. That would be the most natural. The facades are already close to that.

How to use facade such that there is an ambient method?

• Do you really want to impose a .grade() method in each of the graded component?

Yes, this should be coherent with the degree.

• On the other hand, I think that there should be a special mechanism in SetsWithGrading to be able to specify any restriction on the category of the graded components. That would be the most natural and certainly the easiest to implement.

I'm not sure to understand what you mean.

It seems natural to have GradedComponent as a nested class of SetWithGrading, right? (There is no reason that it appears elsewhere.)

I don't think that this GradedComponent should exist. As I said above, it would be better to have something to be able to specify an ambient parent.

Ok, so have you any idea about how to do that? (I don't understand the mean facade or if I understand this is useless... this is just a definition without any code...)

[...]
When we will converge to something reasonable, it would be better to split the features:

• a ticket to implement being subset of a parent (i.e. the ambient method)
• a ticket to implement the category restrictions on the slices
• etc

The most important is to actually not focus on your particular case if you want to implement something useful for categories.

Please, could you provide this splitting and propose some code to start? (I'm lost in the sage maze... show me the line)

I don't care about the path, but at the end, a denumerable set C (or any other name which means graded set with finite graded component) should provide (from a category) a method: CJ = C.graded_component(J) (with J an index whatever the grading set) and from this graded component we should go back to the facade CJ.ambient() == C and we must be able to control that CJ in FiniteSets().

[zabrocki]

comment:22

I think you cheated a little bit with your implementation on Compositions. On master I see:

sage: Compositions(3)([4,1])
...
ValueError: [4, 1] not in Compositions of 3

On this branch

sage: Compositions(3)([4,1])
[4, 1]

You can see why, because you overwrote the _element_constructor_ method in Compositions_n and made it a little too simple. I tried to do a similar change on Partitions and I was getting doc test failures for not having a grade in certain classes. Maybe we can talk about if it is possible to make this a little easier to implement on particular classes.

[sagetrac-git]

Changed commit from c13301a to 6be8fde

[sagetrac-git]

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

6be8fde

ticket 17367: fix the classcall method such that an element is a subclass of parent.element_class

[sagetrac-git]

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

445ba61

ticket 17367: fix element_constructor method of compositions

[sagetrac-git]

Changed commit from 6be8fde to 445ba61

[sagetrac-elixyre]

comment:25

Replying to @zabrocki:

I think you cheated a little bit with your implementation on Compositions. On master I see:

sage: Compositions(3)([4,1])
...
ValueError: [4, 1] not in Compositions of 3

On this branch

sage: Compositions(3)([4,1])
[4, 1]

You can see why, because you overwrote the _element_constructor_ method in Compositions_n and made it a little too simple. I tried to do a similar change on Partitions and I was getting doc test failures for not having a grade in certain classes. Maybe we can talk about if it is possible to make this a little easier to implement on particular classes.

I have fixed that:

sage: Compositions(3)([4,1])
Traceback (most recent call last):
...
ValueError: `[4, 1]` should be an element of Compositions of 3

Replying to @sagetrac-elixyre:

Replying to @videlec:

[...]
When we will converge to something reasonable, it would be better to split the features:

• a ticket to implement being subset of a parent (i.e. the ambient method)
• a ticket to implement the category restrictions on the slices
• etc

The most important is to actually not focus on your particular case if you want to implement something useful for categories.

Please, could you provide this splitting and propose some code to start? (I'm lost in the sage maze... show me the line)

Vincent, could you take some time to answer us your plan about this ticket?

[sagetrac-git]

Changed commit from 445ba61 to 2e03999

[sagetrac-git]

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

2e03999

ticket 17367: update tuto