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.

• Meta ticket: unified sequence/lazy list objects #16107 is the meta-ticket for lazy lists, refactoring the species code, should cross check with major improvements to lazy power series #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 Symmetric functions in several alphabets #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 Implement group cycle indices #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

[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_{n_1} \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.

[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[Id_U] = 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.

[Sandstorm831]

Please have a look @mantepse

[Sandstorm831]

$\alpha_n \cdot U$ application of sequence of group actions $\alpha_n$ on the sequence the set $U$.
let $\alpha_x$ as one of the group action of $\alpha_n$ then
$\alpha_n \cdot U =$ { $\alpha_x \cdot U$ | $\forall x \in [n]$} where $[n] = (1,2,3..,n)$ and $\alpha_x \cdot U$ is the application of group action $\alpha_x$ on the set $U$ , here $U$ is a set, but in $\alpha_n \cdot U$ it is sequence of set of given to species.

[Sandstorm831]

@mantepse please have a look now

[Sandstorm831]

$\alpha_n \cdot U$ can be defined as $\alpha_n \cdot U = \alpha_n(\sigma_n, U)$ where $U$ is a sequence of set given to species and $\sigma_n$ is the sequence of group elements of $\mathfrak S_n$
I think this is what I can call a definition of $\alpha_n \cdot U$, and is best of my understanding.
I have tried to look up in the book also, but I can't relate the statement of question you have asked to the statement they have written in it.
please have a look @mantepse

[Sandstorm831]

@mantepse , can I answer this question afterwards, as currently I am engaged in writing the project proposal regarding this project and need some help.

• How table of marks related to addition and multiplication of burnside ring, I have found something here, can you confirm if it is right or not.
• Do I have to make some wrapper class of Usian-Boltz in sagemath, or implement the usain boltz library inherently.
• In the task support for multivariate species and exhaustive generation of isomorphism types for compositions of species do we have to implement atomic and molecular decomposition of species and especially of the species implemented explicitly as otherwise it would take very long.

[Sandstorm831]

@mantepse , I have tried my level best for this. I don't know what lead you to this conclusion, but I hope you find a suitable person for this project. I will try for some other project in sagemath.
Thanks and Regards

[Newtech66]

Hi! I would like to preface this by saying I am a prospective GSoC applicant for SageMath. That being said...

I have taken an introductory course in abstract algebra, so I have a basic background in group theory, ring theory, and field theory. I also know a little bit of character theory, but I think I can learn it more in depth quickly. However, I do not have any background in combinatorial species (yet).

Given the above, I'd like to try my hand at implementing the Burnside ring. I'm not sure what functionality is required by "implementing" it. I took a look at this thread from 2021. So, is it functionality like what was requested there?

Also, how can I contact you? What kind of discussion is this thread appropriate for? Looking forward to hearing from you!

[Newtech66]

Bump @mantepse

[mantepse]

Hi @Newtech66, sorry for the delay, I was at a conference.

Concerning the Burnside ring: elements are formal sums of isomorphism classes of group actions of a given group $G$ on finite sets. The implementation should provide several means to create ring elements, most importantly by specifying the group action explicitly. For example

# set up the action
sage: G = SymmetricGroup(4)
sage: X = Subsets(4, 2)
sage: a = lambda g, x: X([g(e) for e in x])
# mockup
sage: B = BurnsideRing(QQ, G)
sage: b = B(action=a, domain=X)
sage: b.marks()
(6, 2, 2, 0, 0, 2, 0, 0)
sage: b.group()
Permutation Group with generators [(3,4), (1,2)]

[mantepse]

Here is a brute force implementation without any bells and whistles:

    W = CoxeterGroup(["B", n], implementation = "matrix")
    G = W._gap_()
    tom = G.TableOfMarks()
    C = tom.GeneratorsSubgroupsTom()[1].Length()
    vec = []
    for i in range(1, C+1):
        H = tom.RepresentativeTom(i)
        fix = 0
        for x in X:
            iterator = H.Iterator()
            while not iterator.IsDoneIterator().sage():
                w = W(iterator.NextIterator())
                if not action(w, x) == x:
                    break
            else:
                fix += 1
        vec.append(fix)
    tom.DecomposedFixedPointVector(vec)

[Newtech66]

Ok, here's what I understand:

In the brute force implementation, first we are creating a Weyl group of type $B_n$ as a matrix group acting on some ambient space. Taken directly from Sage, this is my first time trying to understand Coxeter groups.

The point is, we can build a table of marks for this group. So next we interface with GAP and get the Table of Marks.

A ring element of the Burnside ring of a group $G$ is given by $$\sum^{N}_{i=1} a_i [G/G_i]$$ where $a_i$ belongs to $\mathbb{Z}$ and $G_i$ is a representative of a conjugacy class of subgroups of $G$. My question here is, if Wikipedia says $a_i$ belongs to $\mathbb{Z}$, why are we using QQ (the rationals) in the mockup code?

Now enters the group action. We take a set $X$ on which we define the action of the group $\cdot : G \times X \rightarrow X$. The rest of the code, I didn't understand every line (the ones with iterators), but the gist is that we create the row vector of marks $u$ (which is, for each representative of a conjugacy class of subgroups, we evaluate the number of elements of $X$ which are left unchanged by the action of every element of the representative).

According to Wikipedia, we can now decompose $X$ into disjoint copies of orbits of type $G_i$, that is, we can get $a_i$ using the relation $aM=u$. That is what DecomposedFixedPointVector is doing. So now we have a ring element of the Burnside ring of $G$.

[Newtech66]

b.marks() is clearly the row vector of marks as mentioned earlier. Could you please explain the output of b.group()?

@mantepse (Is it necessary to tag someone to notify them of a reply in a thread? Please let me know if I shouldn't do this.)

[mantepse]

Just to make it completely clear: what I wrote is a mockup, so better method names may exist. b.group() should return a representative of the conjugacy class of subgroups of the symmetric group corresponding to the given action. The W in my silly implementation could be just any group. It happened to be the hyperoctahedral group, because at the time I was experimenting with it.

Tagging is only necessary if the tagged person was not involved in the issue before.

[Newtech66]

After completing this task, I can study about combinatorial species and cycle index series and try to provide the quotient species from G-species as required from #14347.

I plan to use the following reference: https://arxiv.org/abs/1312.0542

[mantepse]

An Implementation of this is already available. It only has to be integrated.

[Newtech66]

More questions:

1. What do you mean by integration of the implementation? How long would this take?
2. I also have an interest in (a) implementing the notion of polynomial species and (b) establishing link to permutation groups, and thus providing the molecular/atomic decomposition of a species of fixed cardinality and thereby also decidable equality. I have looked at the paper you linked earlier for molecular/atomic decompositions, and I think it will take me about 1 week to familiarise myself with the math. It would be great if you could point to resources for polynomial species.
3. Could you also tell me what kind of work has already been done, and what needs to be done for the above two tasks?

[mantepse]

1. I don't know. Anything from a day to a week, but it is not clear whether this is worthwhile right now.
2. To implement the molecular decomposition we essentially need the Burnside ring. A polynomial species is just a species for which $F[n]=\emptyset$ when $n$ is large enough. There is nothing to do here.

The tasks really are as follows:

1. implement the Burnside ring. A rough implementation should not take maybe a week or two, which includes time to make yourself familiar with the coding practices and the fundamental structures in sage.
2. implement the molecular decomposition for univariate species.
3. work out how to implement multivariate species.
4. work out how to obtain isomorphism types of operations other than sum and product.

Items 3 and 4 are partially pen and paper work, and the hardest tasks. To make the project a success, I suspect that anybody tackling this would have to start thinking about them very soon, long before the actual coding.

Item 4 may be linked to 'tilde' species, as defined on page 310, Definition 1 of the book. The problem I currently have with this definition is that $\tilde F$ has a huge number of structures: $n!$ times the number of isomorphism types of $F[n]$. So, this is very beautiful from a mathematical point of view, but possibly impractical to work with on a computer.

Currently, the isomorphism types are programmed for each species and for each operation on species separately. In particular, the isomorphism types of a sum (or product) happen to be the pairs of isomorphism types of the two summands (respectively factors). But this does not work for other operations - using the 'tilde' species would always work.

Alternatively, we can obtain the isomorphism types of the substitution species (as in section 1.4 of the book) if we can obtain the isomorphism types with respect to a Young subgroup of the symmetric group of a species. But I am not sure whether this is the correct way to do it.

[Newtech66]

Where in the book can I find a discussion of multivariate species?

[mantepse]

That's 2.4. Extension to the Multisort Context. Personally, I find the name multisort OK, but multiset (definition 2) misleading. A multiset in the sense of the book is simply a tuple of sets of labels.

[mantepse]

Hi @Newtech66, did you get the zoom link?