search

oscar-system / Oscar.jl

A comprehensive open source computer algebra system for computations in algebra, geometry, and number theory.
https://www.oscar-system.org
Other
344 stars 126 forks source link

Basic combinatorics in OSCAR #3147

Open joschmitt opened 9 months ago

joschmitt commented 9 months ago

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 https://github.com/oscar-system/Oscar.jl/pull/3021#discussion_r1399151945 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 commented 9 months ago

Maybe @ulthiel is interested in this as well.

lgoettgens commented 9 months ago

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 commented 9 months ago

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 commented 9 months ago

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 commented 9 months ago

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 commented 9 months ago

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

jankoboehm commented 9 months ago

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 commented 9 months ago

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 commented 9 months ago

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.

:+1: I put it in the Hackmd so we don't forget about it.

joschmitt commented 9 months ago

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 commented 9 months ago

This general approach should resolve https://github.com/oscar-system/Oscar.jl/issues/2301 as well.

joschmitt commented 9 months ago

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 commented 9 months ago

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: https://github.com/oscar-system/Oscar.jl/issues/3147#issuecomment-1881088087 You are receiving this because you are subscribed to this thread.

Message ID: @.***>

ulthiel commented 9 months ago

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 https://github.com/oscar-system/Oscar.jl/pull/3021#discussion_r1399151945: 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...).