Metaticket for combinatorial species

[mantepse]

In preparation for a long needed overhaul (and a workshop in early 2021 I am planning), let's collect tickets and issues related to combinatorial species here. An earlier roadmap is #10662. An earlier attempt to refactor the species code is #20622.

• 16107 is the meta-ticket for lazy lists, refactoring the species code, should cross check with #15673

• improve operations with symmetric functions - it would be particularly nice if a cycle index would just be a symmetric function, so we can immediately use their operations

• implement the notion of polynomial species (that is, species with F[n] = {} for n large enough), so that we can compute the composition of a polynomial species with a species that has non-zero constant term.

• multivariate species, see #13264

• provide isomorphism types for composition (which probably needs multivariate species or quotients)

• establish link to permutation groups, and thus provide the molecular/atomic decomposition of a species of fixed cardinality and thereby also decidable equality

• keep track of symbolic expressions for generating functions

• revive group cycle index #14347 - a big issue is that this code only provides the cycle index series, not the quotient species themselves

• interface to https://gitlab.com/ParComb/usain-boltz for random generation

• allow sets as input for structures, possibly also use _getitem_ for structures, create a class for bijections between finite sets which we can use to relabel structures

• provide the arithmetic product on the level of structures

• provide the exponential composition of https://arxiv.org/abs/0705.0038

• species for other groups, in particular the hyperoctahedral group

CC: @slel @sagetrac-tmonteil @MatthieuDien

Component: combinatorics

Keywords: species

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

[mantepse]

Description changed:

--- 
+++ 
@@ -17,3 +17,5 @@
 * species for other groups, in particular the hyperoctahedral group

 * interface to https://gitlab.com/ParComb/usain-boltz for random generation
+
+* allow sets as input for structures, possibly also use `_getitem_` for structures

[mantepse]

Description changed:

--- 
+++ 
@@ -18,4 +18,4 @@

 * interface to https://gitlab.com/ParComb/usain-boltz for random generation

-* allow sets as input for structures, possibly also use `_getitem_` for structures
+* allow sets as input for structures, possibly also use `_getitem_` for structures, create a class for bijections between finite sets which we can use to relabel structures

[mantepse]

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@

 * keep track of symbolic expressions for generating functions

-* revive group cycle index #14347
+* revive group cycle index #14347 - a big issue is that this code only provides the cycle index series, not the quotient species themselves

 * species for other groups, in particular the hyperoctahedral group

[mantepse]

Description changed:

--- 
+++ 
@@ -1,21 +1,26 @@
 In preparation for a long needed overhaul (and a workshop in early 2021 I am planning), let's collect tickets and issues related to combinatorial species here.  An earlier roadmap is #10662.  An earlier attempt to refactor the species code is #20622.

-* #16107 is the meta-ticket for lazy lists, refactoring the species code should cross check with #15673
+* #16107 is the meta-ticket for lazy lists, refactoring the species code, should cross check with #15673

 * improve operations with symmetric functions - it would be particularly nice if a cycle index would just be a symmetric function, so we can immediately use their operations

 * multivariate species, see #13264

-* provide isomorphism types for functorial composition (which needs multivariate species)
+* provide isomorphism types for composition (which probably needs multivariate species or quotients)

-* establish link to permutation groups, and thus provide the molecular/atomic decomposition of a species of fixed cardinality
+* establish link to permutation groups, and thus provide the molecular/atomic decomposition of a species of fixed cardinality and thereby also decidable equality

 * keep track of symbolic expressions for generating functions

 * revive group cycle index #14347 - a big issue is that this code only provides the cycle index series, not the quotient species themselves

-* species for other groups, in particular the hyperoctahedral group
-
 * interface to https://gitlab.com/ParComb/usain-boltz for random generation

 * allow sets as input for structures, possibly also use `_getitem_` for structures, create a class for bijections between finite sets which we can use to relabel structures
+
+* provide the arithmetic product on the level of structures
+
+* provide the exponential composition of https://arxiv.org/abs/0705.0038
+
+* species for other groups, in particular the hyperoctahedral group
+

[mantepse]

Description changed:

--- 
+++ 
@@ -3,6 +3,8 @@
 * #16107 is the meta-ticket for lazy lists, refactoring the species code, should cross check with #15673

 * improve operations with symmetric functions - it would be particularly nice if a cycle index would just be a symmetric function, so we can immediately use their operations
+
+* implement the notion of polynomial species (that is, species with F[n] = {} for n large enough), so that we can compute the composition of a polynomial species with a species that has non-zero constant term.

 * multivariate species, see #13264

[mkoeppe]

comment:10

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[mantepse]

The book https://www.cambridge.org/core/books/combinatorial-species-and-treelike-structures/D994A1F2877BDE63FF0C9EDE2F9788A8 gives you a gentle introduction. Chapter 5 is not relevant.

One project is the implementation of the https://en.wikipedia.org/wiki/Burnside_ring of a finite group. This is completely separate from combinatorial species, but will be a necessary tool. I would hope that we can use gap to do the actual computations: https://docs.gap-system.org/doc/ref/chap70.html. If you are interested in doing some mathematics, it might be fun to start playing with this right away. The Burnside ring takes a finite group as input. Its elements are then the conjugacy classes of subgroups, and you have to implement addition and multiplication, using the table of marks.

https://www.sciencedirect.com/science/article/pii/0097316589900198 is an article clarifying the connection with combinatorial species. The relevant section of the book by Bergeron, Labelle and Leroux is 2.6. Using this, it is possible to obtain the molecular / atomic decomposition of a species. Of course, for a general species this will be incredibly slow, and doable only if the size is very small. However, for the species which are implemented explicitly we could then implement the molecular / atomic decomposition just as we currently implement the Frobenius character (also known as cycle index series).

One major goal is to be able to compute isomorphism types of structures with respect to an action of a Young subgroup (i.e., $\mathfrak S_{n1} \times \dots \mathfrak S{n_k} < \mathfrak S_n$ of the symmetric group, not just the full symmetric group. As a special case, we will then be able to list isomorphism types of structures of compositions of species, which is currently not possible.

I know very little about random generation, and I have no clear picture on how to interface with Usain-Boltz. I believe, the main difficulty here is to work out this interface, and I would not be surprised if this is hard to get right.

[Sandstorm831]

Thank you @mantepse for such a detailed response. I would be definitely interested in implementing and learning the mathematics behind burnside_ring. I have a few questions, can you tell me what are the prerequisites of the book that you have linked, so that I could start working on them right away. Can you tell me issues_number that deal with the concepts you mentioned so that I could start understanding the code-base also related to this.

[mantepse]

There are no prerequisites for the book. For group actions in general, i am not sure what a good reference might be.

[Sandstorm831]

Thank you @mantepse for your response, I will start working on it right away.

[mantepse]

A first guiding question for your study: given a combinatorial species, define the corresponding permutation group / group action of the symmetric group, and conversely. If you have questions, math.stackexchange may be a good place.

[Sandstorm831]

Can I answer this question afterwards, as It will take some time to read the book. Also @mantepse can you provide me any means of contacting you other than github and mail.

[Sandstorm831]

@mantepse , Upto the point I have read the book, and thought of the question, I had came up with following:

The permutation group of a species $F$ would be the set $F[U]$ combined with group operation which is the composition of all mappings from $\sigma : U \to V$ which is nothing but $F[\sigma]$, whereas V coincides to U but is a permutation of U. This also satisfies the group actions axioms, let $s \in F[U]$ be a $F$-structure of $U$ and $g: U \to V$ and $h: V \to W$ where $V$ and $W$ are permutations of $U$, by definition of species, we have $F[g \circ h] = F[g] \circ F[h]$ which denote the same meaning as $(g \circ h) s = g \circ (h \circ s)$. For the second identity, we have $id_U \circ s = s$ which give the same meaning as by definition of species on a identity map $Id_U : U \to U$ we have $F[IdU] = Id{F[U]}$, thus completing the definition.

Previous definition : Let $s \in F[U]$ be a $F$-structure on $U$, where $U$ is a finite set. The permutation group of a species $F$ would be the set $F[U]$ combined with group operation which is the composition of all identity mappings $U \to U$ which is nothing but $F[Id_{U}]$.

previous definition : for a given structure $s = (\gamma, {U})$, where ${U}$ is the underlying set, and $\gamma$ is the construction. The specie $F$ is a rule, whereas $F[U]$ is finite set of structures on a finite set $U$ and $F[\sigma]$ is a function of transportation of each structure of $F[U] \to F[V]$ where $\sigma$ is bijection $\sigma: F[U] \to F[V]$. We can define a permutation group corresponding to $F[U]$ as the set of all the structures of $F[U]$ and corresponding group action is the bijection $Id_{F[U]}$

This is the best I can understand by the meaning of permutation group corresponding to a specie. Forgive me if it is wrong, and please let me know the correct meaning of it.

[mantepse]

I was not expecting you to answer this question immediately, take your time! I suggest that you improve your answer by editing the comment, and once we got it right, I will delete my comments.

A minor thing: the singular of "species" is "species", so it is "a species".

I am not sure whether it makes sense to say that a structure comes with a "construction". It might, but this is not necessary. So it is better to say: $F$ is a species (as defined on page 5, Def. 3) and $s\in F[U]$ is an $F$-structure on $U$.

I like to call $F[\sigma]$ a relabelling of $F$-structures.

There is one important mathematical typo in the last line. You will have to look up the definition of permutation group (eg. wikipedia, it also contains a definition of group action).

To continue, just edit your answer whenever you are ready!

[Sandstorm831]

@mantepse can you recommend any book for understanding permutation group, group action and similar concepts.

[mantepse]

What's wrong with the Wikipedia page?

[Sandstorm831]

nothing, just the thing is I am more used to books.

[Sandstorm831]

@mantepse , please check my new definition this time.

[mantepse]

No, it is still incorrect. $F[id_U]$ would be the identity on $U$. What you need is a map $\rho: \mathfrak S_n \times F[n] \to F[n]$, where $F[n] := F[{1,\dots,n}]$ and $\mathfrak S_n$ is the symmetric group on $n$ letters. Additionally, this map must satisfy the group action axioms.

[Sandstorm831]

Ok, I need to correct my group operation. I need a group operation that could map all the structures of $F[U]$ as well as it satisfy the group action axioms which are identity, compatibility, associativity

[mantepse]

There is no associative axiom in the definition of a group action. We have $id_{\mathfrak S_n}\cdot s = s$ and $g\cdot (h\cdot s) = (g h)\cdot s$.

[Sandstorm831]

There is no associative axiom in the definition of a group action. We have idSn⋅s=s and g⋅(h⋅s)=(gh)⋅s.

first one is the identity axiom but what $g⋅(h⋅s)=(gh)⋅s$ is called?

[mantepse]

wikipedia calls it "compatibility". I don't know whether this name is commonly used. In any case, this is not an associative law.

[Sandstorm831]

@mantepse , updated again. please have a look.

[mantepse]

OK, this looks essentially correct. There is one glitch: it is good practice to distinguish between the group operation (i.e., the multiplication of two group elements) and the group action (i.e., the operation of a group element on an element of the finite set). In your text, these are confused.

It is also good practice to use the same font or alphabet for a given set of objects.

Finally, to clarify thoughts, it is good to be less verbose. The important questions are as follows:

Given a combinatorial species $F$, we can define, for every $n\in\mathbb N$ a group action as follows:

• what is the group acting?
• which set does it act on?
• how is the action defined?

Each of these questions can be answered in a few symbols.

After that, we can go further:

Equivalently, we can define, for every $n\in\mathbb N$ a permutation group as follows:

• what is the finite set?
• what are the group elements of the permutation group?

Finally, given a permutation group $G < \mathfrak S_n$, for $n\in\mathbb N$, we can define a combinatorial species $F$ as follows:

• given a finite set $U$, what is $F[U]$? (hint: how can we regard a permutation group as a group action?)
• given finite sets $U$ and $V$, an element $f\in F[U]$ and a bijection $\sigma: U \to V$, what is $F[\sigma](f)$?

[Sandstorm831]

Thank you @mantepse , I was confused and used both group actions and group operations interchangeably, now I have got that, I have to use group action instead of group operation.

I will answer those questions accordingly.

[mantepse]

It is confusing, because some people use "group operation" for what I call "group action". So, you are in good company.

[Sandstorm831]

I am also getting confused, since my definition is not including 2 group elements as a group operation must have. It is now clear that group action is the correct term for what I am calling group operation.

[mantepse]

I suggest to use $\sigma \cdot f$ for the group action and $\sigma \tau$ for the group multiplication (i.e., group operation). In particular, I use a one alphabet for the group elements (e.g., lowercase greek) and a different alphabet (e.g., lowercase latin) for the elements of the set my group is acting on.

Since $\circ$ is commonly used for an operation on species (plethysm, also known as composition), I avoid to use it for other things.

[Sandstorm831]

Given a combinatorial species $F$, we can define, for every $n\in\mathbb N$, a group action as follows:

---

what is the group acting? $\mathfrak S_n$ which set does it act on? $F[n]$ how is the action defined? group action $\alpha : \mathfrak S_n \times F[n] \to F[n]$ is defined as: $\sigma \cdot f := F[\sigma] (f)$ where $\sigma \cdot f = \alpha(\sigma, f)$ and $F[n]=F[{1,2,3,...,n}]$

---

Equivalently, we can define, for every $n\in\mathbb N$ a permutation group as follows:

What is the finite set? $F[n]$,

What are the elements of the permutation group permutations of the elements of $F[n]$

---

Given a permutation group $G <\mathfrak S_n$, for $n\in\mathbb N$, we can define a combinatorial species $F$ as follows:

Given a finite set $U$, what is $F[U]$ ?(hint: how can we regard a permutation group as a group action) Since $G$ is a permutation group such that $G<\mathfrak S_n$, for any $g \in G$ would be a permutation which could be equivalently regarded as a bijection. Now given a set $U$, $F[U]$ can be defined as $F[U] = ${ $g\cdot U || \forall g \in G$}

given finite sets $U$ and $V$ , an element $f\in F[U]$ and a bijection $\sigma: U \to V$ , what is $F[\sigma] (f)$ ? Similarly, as $\sigma$ is a bijection from $U \to V$, we also have $g \in G$ which is another bijection. Since $f \in F[U]$, therefore $f = g \cdot U$ for some $g \in G$ Thus we can define $F[\sigma] (f) = \sigma (g \cdot U) = (\sigma \cdot g) U$

---

@mantepse, These are the answers according to my initial thinking about the questions, please check, and if found wrong, provide some feedback so as to move forward in the right direction.

[mantepse]

I am extremely sorry, but all answers above are (entirely) wrong. This is a bit surprising to me, because your last attempt was not completely off.

I am not sure how I could help.

[Sandstorm831]

@mantepse can you tell me what does what is the group acting? mean And is my assumption of $N$ as the set of first of first $n$ natural numbers and basing my definition on it is correct ??

[mantepse]

Did you read the wikipedia pages I linked to? You could also read Appendix 1 of the book by Bergeron, Labelle and Leroux.

[Sandstorm831]

@mantepse I have updated all my answers, previous answers are completely disasters and I got to know why because they were my initial thoughts and haven't consulted resource. I have consulted the appendix 1 and wikipedia page and some additional material. please have a look.

[Sandstorm831]

Also @mantepse can you provide a template for writting the project proposal for GSoC, or I only have to write completely from scratch.

[mantepse]

Dear @Sandstorm831, I am sorry, but this doesn't work out. The answers are still not correct. Most importantly, the answer to the first question (how to define a group action given a species) doesn't even make sense. If I tell you that the definition of the group action is $\alpha_n: \mathfrak S_n\times F_n \to F_n$, how would you implement this? This answer doesn't carry any information, even if I guess what $F_n$ might be.

I am not sure how to proceed, but at the moment I do not see how you would be able to solve the problems with the species code. I mentioned in the problem description that this is not an easy problem.

[Sandstorm831]

@mantepse i might not be able to put my thoughts to words But this is what I think of when you asked me 1st question of defining a group action As i have given a species F and a natural number N, for defining a group action, i would need a symmetric group of n elements, named Sn, then, for a group action to act, we need a set, it can be set of structure and with a natural number n I can think of F[n] as the set of structures having n as their cardinality. Since a Sn is stmmmetric group having permutations as elements and since each permutation can be thought of as a bijection, we can thought of acting this as group action where each permutation act as bijection on the set of structures F[n]. So we define this group action $\alpha_n: \mathfrak S_n\times F_n \to F_n$

Please tell if this is correct or not, and if not please correct me in this definition.

[Sandstorm831]

In my previous answer $F_n$ is nothing but $F[n]$, i have seen this notation used somewhere, so my fault.

Talking of problem mentioned in the project, It's my first time encounter to abstract algebra and discrete mathematics, so it's taking me some time, but within a few weeks, I would be doing things smoothly. As in case of supergreedy, it took 8-10 days understanding the mathematics and only 4-5 days writing the main functioning code.

[mantepse]

I don't know what you mean with $F_n$, and I don't know what you mean with the set of structures having $n$ as their cardinality.

What I was hoping for was something similar to the following:

Let $F$ be a species and $n$ a natural number. Then we define a group action of the symmetric group as follows. $\rho:\mathfrak S_n\times F[n] \to F[n]$, $\sigma\cdot f := F[\sigma](f)$, where $\sigma\cdot f$ is short for $\rho(\sigma, f)$ and $F[n]$ is short for $F[\{1,\dots,n\}]$.

[Sandstorm831]

Hey @mantepse , Please have a look at my updated answer.

[Sandstorm831]

Please have a look @mantepse

[Sandstorm831]

Dear @mantepse , please give me some comment. if the answers are incorrect, then I have to look again at all the definitions, because this time, I don't think my answers are wrong.

[mantepse]

I already gave a complete answer to the first question above. In your updated answer, I don't understand why you introduce $F_n$, $\alpha$ and $\alpha_n$. I am guessing that the latter two are the same, but after so many attempts I would have hoped that you would try to be very precise.

The second question was how to define a corresponding permutation group. The set is $F[n]$, and the elements of the group are the permutations $F[\sigma]$ for $\sigma\in\mathfrak Sn$. In particular, the permutation group is a subgroup of $\mathfrak S{F[n]}$.

The third question was to define a combinatorial species given a subgroup $G$ of $\mathfrak S_n$. Here, I actually made a mistake in the phrasing of the question, because the way it is stated, it is not possible. Given $G$, there is obviously no way to know the cardinality of the set of labels. For example, if $G$ consists only of the identity in $\mathfrak S_2$, we could have the species which has two structures for any input set $U$, together with the trivial action.

What I should have asked for is to construct a species given a sequence of group actions $\mathfrak S_n \times F_n \to\mathfrak S_n$ where $F_n$ is a sequence of finite sets. This is exactly exercise 2.6.27e in the book.

[Sandstorm831]

@mantepse, thank you helping me learn the subject, I am sorry for the errors present in answers of first part, $\alpha_n$ was a mistake, and I intended to write only $\alpha$, also I just forgot to correct the $F_n$ to $F[n]$, so my fault.

In the second part of second question, I have written "permutations of $F[n]$" which is not helpful to calculate elements of the group, my fault in that, can you explain what you mean by the group $\mathfrak S{F[n]}$, did it mean a symmetric group on the elements of $F[n]$

In the rephrased 3rd question, by the phrase "a sequence of group actions $\mathfrak S_n \times F_n \to \mathfrak S_n$ where $F_n$ is a sequence of finite sets" did you mean the sequence of group actions as follows: $\alpha_i: \mathfrak S_n \times F_i \to \mathfrak S_n$

[Sandstorm831]

Given a sequence of group actions $\alpha_n : \mathfrak S_n \times F_n \to \mathfrak S_n$, where $F_n$ is the sequence of finite sets. We can define a species $G$ as follows: Given a set $U$, $G[U] = (\alpha_n \cdot U )$, which is set of structures generated by sequential application of each group action on the given set $U$. For the bijection $\sigma : U \to V$ we have $F[\sigma] = \sigma \cdot (\alpha_n \cdot U) = (\sigma \cdot \alpha_n) U$

@mantepse please check if this is correct.

[Sandstorm831]

@mantepse can you have a look at my answer please

[Sandstorm831]

@mantepse, please have a look now

[mantepse]

I don't understand what $\alpha_n\cdot U$ is supposed to mean. As I wrote above, you can check exercise 2.6.27e in the book for a solution.

[Sandstorm831]

$\alpha_n \cdot U$ represent action of the sequence of group actions over the set $U$

[Sandstorm831]

@mantepse please have a look