Basic combinatorics in OSCAR

[joschmitt]

I put some ideas together how we could improve the functionality of basic combinatorics in OSCAR, see https://hackmd.io/Ef1t9wjbQwWlkrL4DQgYxQ . Please edit and comment on anything you can think of there (assuming I set the permissions correctly).

For me, the motivation is the discussion in #3021 (comment) and the subsequent discovery that we have at least three implementations of 'weak compositions of d in n parts' floating around.

See also #1732.

[lgoettgens]

Maybe @ulthiel is interested in this as well.

[lgoettgens]

Personally, I would like to see most of this upstream, maybe in AbstractAlgebra, so that we don't need additional implementations of some things in AA and Hecke.

[thofma]

I would suggest we first get something consistent here in OSCAR and afterwards start thinking about moving things around. The focus before 1.0 should be on a final API (which is independent of where the things reside).

[mjrodgers]

I'd be interested in helping work on this, both the basic combinatorial functions and various q-analogs.

I see there is some q-analog stuff in JuLie that hasn't been migrated to experimental, I would vote that if we bring this over, these functions are renamed to not use the term quantum. I think it is most common to just call these q-factorial, q-binomial, etc.

[joschmitt]

I'd be interested in helping work on this, both the basic combinatorial functions and various q-analogs.

I see there is some q-analog stuff in JuLie that hasn't been migrated to experimental, I would vote that if we bring this over, these functions are renamed to not use the term quantum. I think it is most common to just call these q-factorial, q-binomial, etc.

Great! I don't know much about combinatorics, so any help by somebody who knows this stuff is very welcome.

[thofma]

Let me also ping @lkastner: is there anyone in Berlin that has some input on the API question for combinatorics?

[jankoboehm]

I would be interested in this. I would like to use it in particular in my class on combinatorics for computer science (which would require to have an easy to use and stable user interface and docu). Next iteration of the class is in the coming summer. Some thoughts:

First of all, combinatorics is about numbers, so we should also have functions which give you the number of the objects under consideration. Some are given by closed expressions, others through recursions, etc.

Most identities of numbers come from bijections. Those give you algorithms to enumerate the objects. I agree that we should return iterators, but for ease of use there might also be an argument to have in addition a function which just gives them all.

It would also be interesting (in particular for didactical purposes) to have functions which yield the underlying bijections (say e.g. the map between sets of Young diagramms yielding a recursion for partitions, as well as numbers of partitions).

[StevellM]

Related to the original problem for hyper-complexes and related to the comment of Lars K., there something I have implemented some time ago: https://github.com/oscar-system/Oscar.jl/blob/master/experimental/SymmetricIntersections/src/elevators.jl. The name is a bit random. Eventually, it would be great if the combinatorics features could replace this experimental code. The idea is the following:

Given an (ordered) list L of positive integers, and an integer d, return an iterator on the tuples of indices for which the corresponding elements in L sum up to d. Each index can be repeated, and one could ask to have an upper (and lower?) bound on the number of time each index should be used. I implemented that to enumerate all characters of a finite group of a given degree, or all constituents of a given character.

I wrote it with the help of Lars K. who helped me for the Polymake side. At the end I guess it is related to the monomials_of_degree stuff. I am not sure how relevant it is to put it on the HackMD, I would at least let you know about this other piece of combinatorics hidden in Oscar.

[joschmitt]

Related to the original problem for hyper-complexes and related to the comment of Lars K., there something I have implemented some time ago: https://github.com/oscar-system/Oscar.jl/blob/master/experimental/SymmetricIntersections/src/elevators.jl. The name is a bit random. Eventually, it would be great if the combinatorics features could replace this experimental code. The idea is the following:

Given an (ordered) list L of positive integers, and an integer d, return an iterator on the tuples of indices for which the corresponding elements in L sum up to d. Each index can be repeated, and one could ask to have an upper (and lower?) bound on the number of time each index should be used. I implemented that to enumerate all characters of a finite group of a given degree, or all constituents of a given character.

I wrote it with the help of Lars K. who helped me for the Polymake side. At the end I guess it is related to the monomials_of_degree stuff. I am not sure how relevant it is to put it on the HackMD, I would at least let you know about this other piece of combinatorics hidden in Oscar.

👍 I put it in the Hackmd so we don't forget about it.

[joschmitt]

I see there is some q-analog stuff in JuLie that hasn't been migrated to experimental, I would vote that if we bring this over, these functions are renamed to not use the term quantum. I think it is most common to just call these q-factorial, q-binomial, etc.

@mjrodgers This sounds like it is related to #2183 .

[lgoettgens]

This general approach should resolve #2301 as well.

[joschmitt]

Regarding moving the partition functionality from experimental/JuLie to src (so #2301): Does anybody know why this has only be moved to experimental in the first place? Or what needs to be done, to make it "good enough" for src? I skimmed the discussion in the original pull requests adding the functionality and I did not see anything. Just going by test coverage, documentation, etc. it looks good to me.

[fieker]

On Mon, Jan 08, 2024 at 06:12:28AM -0800, Johannes Schmitt wrote: Regarding moving the partition functionality from experimental/JuLie to `src` (so #2301): Does anybody know why this has only be moved to `experimental` in the first place? Or what needs to be done, to make it "good enough" for `src`? I skimmed the original pull requests adding the functionality and I did not see anything. Just going by test coverage, documentation, etc. it looks good to me.

The people orginally doing that did not dare to aim for non-experimental. They were extremely happy to be restricted to experimental: no risk...

…

-- Reply to this email directly or view it on GitHub: #3147 (comment) You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[ulthiel]

For me, the motivation is the discussion in #3021 (comment) and the subsequent discovery that we have at least three implementations of 'weak compositions of d in n parts' floating around.

Just a remark concerning #3021 (comment): this is basically about compositions of an integer. I have implemented fast algorithms for this in JuLie (and an iterator as well if I remember correctly). This has not been ported to experimental/JuLie, however (no criticism, I could/should have done it myself, but...).

[fieker]

@ulthiel will be contacted, he would be the best candidate to contact

[fieker]

e.g. subsets and MSets in Hecke need to be added into the combinatorics docu..

[fieker]

@lkastner and @mjrodgers are going to deal wth this, possibly before Xmas - or not