Combinatorics: compositions, partitions, Young tableaux, Schur polynomials

[JohnAAbbott]

Describe the bug
Several minor problems (see To reproduce below)

To Reproduce
Steps to reproduce the behavior, please provide a code snippet that triggers
the bug.

using Oscar
# Many problems when trying to specify Int8 entries in partitions/compositions

# number_of_compositions(n)  seems OK  for n Int, Int8, ZZRingElem etc

# compositions(n)  initially OK  for n Int, Int8, ZZRingElem etc  **BUT**

collect(compositions(Int8(4)))     # Error: cannot convert
collect(compositions(ZZ(4)))       # works!

compositions(Int8(4), 2)           # Error: cannot convert
compositions(Int8(4), Int8(2))     # Error: cannot convert
collect(compositions(4, Int8(2)))  # OK :-)

# weak_compositions seem to be OK
collect(weak_compositions(Int8(4), 2))  # OK :-)


# Trouble with filter and partitions iterator

iter = partitions(25);
filter(c -> length(c) == 1, iter)  # MethodError


coins = [1, 2, 5, 10, 20, 50];   # Euro coins
iter = partitions(99, coins);    # iterator over ways of giving 99 cents change
filter(c -> length(c) < 8, iter) # --> MethodError



tab = young_tableau([ [1,2,3,4], [5,6], [7] ])
H = hook_lengths(tab)  # MethodError   (!unfortunate!)
H = hook_lengths(shape(tab));
weight(H)  # BoundsError

tab1 = young_tableau([[-1]]);
is_standard(tab1)      # BoundsError
is_semistandard(tab1)  # works OK

# iterators: just generate a big list internally, not "proper" iterators
std_tab = standard_tableaux(13); # just generates a big list (I guess)
std_tab  # gives Base.Generator{...}
for t in std_tab
  println(t)   # prints out just "Young tableau" (lots of times)
end
# L = collect(std_tab); println(L[1]); # does print out the tableau

P = partition([4,2,1]);
number_of_standard_tableaux(P)
std_tab = standard_tableaux(P);
std_tab[1]   # MethodError

L = collect(std_tab);
L[1]  # works as desired

### --------------------------------------------

# Schur polynomials

# Manual may be wrong: \lambda is a partition with n parts
# (and not a partition of n).  I would also discourage use
# of the schur_polynomial without the ring (because then each
# result is in a different ring, even though the rings look
# the same)

# Not sure if this is really an error, but might trip up the unwary
j = schur_polynomial(partition([3,1]),3);
k = schur_polynomial(partition([2,2]),3);
j == k  # Error: incompatible polynomial rings in polynomial operation


R,_ = polynomial_ring(ZZ, ["x1", "x2", "x3"]);
schur_polynomial(R, partition([48,2]))  # OK
schur_polynomial(R, partition([49,1]))  # OK
schur_polynomial(R, partition([49,2]))  # Error: length of exponent vector should match the number of variables

Expected behavior
No deep maths here.
Questions of UI; some arg checks need strengthening.

System (please complete the following information):
Please paste the output of Oscar.versioninfo(full=true) below. If this does
not work, please paste the output of Julia's versioninfo() and your Oscar
version.

julia> Oscar.versioninfo(full=true)
  combining:
    AbstractAlgebra.jl   v0.41.6
    GAP.jl               v0.10.4
    Hecke.jl             v0.32.0
    Nemo.jl              v0.45.3
    Polymake.jl          v0.11.17
    Singular.jl          v0.23.1
  building on:
    FLINT_jll               v300.100.300+0
    GAP_jll                 v400.1200.200+9
    Singular_jll            v403.216.1603+0
    libpolymake_julia_jll   v0.11.5+0
    libsingular_julia_jll   v0.44.3+0
    polymake_jll            v400.1100.3+0
See `]st -m` for a full list of dependencies.

Julia Version 1.10.2
Commit bd47eca2c8a (2024-03-01 10:14 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 20 × Intel(R) Core(TM) i9-10900 CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, skylake)
Threads: 1 default, 0 interactive, 1 GC (on 20 virtual cores)
Environment:
  JULIA_LOAD_PATH = @:@v#.#:@stdlib:/environments/globalenv
  JULIA_DEPOT_PATH = /home/zez25zuh/.julia:
Official https://julialang.org/ release

Additional context
Probably not urgent; I just need to avoid these problems while preparing the demo.

[joschmitt]

I'll look into it.
And yes, standard_tableaux currently produces a "big list" internally and then returns an iterator over that list. The big list version was implemented in JuLie, copied over from there and afterwards it was decided that these functions should return iterators and not arrays. Then there was the 1.0 release and we needed a quick solution. I'm working on improving this. (Sometimes.)

Regarding that tableaux print as "Young tableau" in one-line mode: They print rather nicely (I fancy) in detailed mode. But in one-line mode, I didn't know what to put. Would something like [[1, 2, 3], [2, 3]] be understandable/helpful? (I never work with these things.)

[JohnAAbbott]

Young tableau is OK for one-line and terse modes, but I was surprised that the println in the loop did not print out the full table; to see what is in the table I had to collect into an array, and the print out the relevant entry in the array.
As hinted, this is not really urgent (i.e. not essential before the Begehung)

[JohnAAbbott]

This example below is unexpected (not doubt a Julia foible):

julia> YT = young_tableau([[1,2],[3]]);
julia> YT
+---+---+
| 1 | 2 |
+---+---+
| 3 |
+---+
julia> println(YT)
Young tableau

I had not realized that println(val) would behave differently from val #=without semicolon=#

[fieker]

there is display and show and a mess

[joschmitt]

Thank you for reporting all this.
I fixed some of these in #3860.

I don't think we can do anything about filter(..., partitions(3)). From what I understand, filter works on collections but not on iterators. (If anyone knows better, please speak up!)

We can easily add a hook_lengths(::YoungTableau). I don't know what interface people want? (Again, I unfortunately don't use this stuff.)

This bit

std_tab = standard_tableaux(P);
std_tab[1]   # MethodError

L = collect(std_tab);
L[1]  # works as desired

is as expected. One day, standard_tableaux will also internally be an iterator, so getindex is not supported.

This

# Not sure if this is really an error, but might trip up the unwary
j = schur_polynomial(partition([3,1]),3);
k = schur_polynomial(partition([2,2]),3);
j == k  # Error: incompatible polynomial rings in polynomial operation

is following the rule that internal polynomial rings must be created with cached = false. Maybe this situation is an exception? I don't know.

[thofma]

I don't think we can do anything about filter(..., partitions(3)). From what I understand, filter works on collections but not on iterators. (If anyone knows better, please speak up!)

Yes, this is correct. This cannot work unless we overload filter, which we should not.

# Not sure if this is really an error, but might trip up the unwary
j = schur_polynomial(partition([3,1]),3);
k = schur_polynomial(partition([2,2]),3);
j == k  # Error: incompatible polynomial rings in polynomial operation

is following the rule that internal polynomial rings must be created with cached = false. Maybe this situation is an exception? I don't know.

I would say that this is working as expected.

[JohnAAbbott]

there is display and show and a mess

Ah! Indeed a mess is perhaps a good description of the situation. According to the Julia doc display should produce the nicest output form, but there's no guarantee about where the output will go (e.g. could be in a new pop-up window). Instead they recommend using the rather verbose show(stdout, "text/plain", x). I'd better document this!

[JohnAAbbott]

I don't think we can do anything about filter(..., partitions(3)). From what I understand, filter works on collections but not on iterators. (If anyone knows better, please speak up!)

Yes, this is correct. This cannot work unless we overload filter, which we should not.

Indeed, meddling with Julia's own functions is probably unwise. The Julia doc about filter is not so clear to me: is says it can be applied to an "iterable object" (whatever that may mean). Presumably iterators are not iterable ?!?

# Not sure if this is really an error, but might trip up the unwary
j = schur_polynomial(partition([3,1]),3);
k = schur_polynomial(partition([2,2]),3);
j == k  # Error: incompatible polynomial rings in polynomial operation

is following the rule that internal polynomial rings must be created with cached = false. Maybe this situation is an exception? I don't know.

I would say that this is working as expected.

I've decided just to skip over this possibility in the demo/tutorial; maybe I'll check/improve the OSCAR doc...

[thofma]

Indeed, meddling with Julia's own functions is probably unwise. The Julia doc about filter is not so clear to me: is says it can be applied to an "iterable object" (whatever that may mean). Presumably iterators are not iterable ?!?

Just to clarify, are you talking about filter or Iterators.filter?

[JohnAAbbott]

Uff! You're right: I wasn't paying attention. Gosh! Why do they have both filter and Iterators.filter? Groan!
Maybe Iterators.filter does what I want? I'll investigate...

[JohnAAbbott]

Regarding that tableaux print as "Young tableau" in one-line mode: They print rather nicely (I fancy) in detailed mode. But in one-line mode, I didn't know what to put. Would something like [[1, 2, 3], [2, 3]] be understandable/helpful? (I never work with these things.)

I have forgotten how many different print modes we have: used to be :oneline and :terse and also the full version. I think it would be better to have something like YoungTableau([[1, 2, 3], [2, 3]]) rather than just Young tableau in "one-line" mode. I note that partitions print out their parts in "one-line" mode.

[joschmitt]

I have forgotten how many different print modes we have: used to be :oneline and :terse and also the full version. I think it would be better to have something like YoungTableau([[1, 2, 3], [2, 3]]) rather than just Young tableau in "one-line" mode. I note that partitions print out their parts in "one-line" mode.

I added something to #3860.

[JohnAAbbott]

This is looking very good now -- thanks, @joschmitt
There is still an error with weight. Specifically

H = hook_lengths(partition([4,2,1]))
weight(H)  # gives  BoundsError

A quick look at the code suggests that it requires that the tableau be semistandard, but does not check this! Either we modify the code so that it checks, or we modify it so that all Young tableaux are accepted. I do also wonder whether the name should be changed to weight_sequence. I have searched quickly on internet: given a YT the weight is a sequence; it may assume that the entries in the YT are positive (or maybe just non-negative).

[joschmitt]

This is looking very good now -- thanks, @joschmitt There is still an error with weight. Specifically

H = hook_lengths(partition([4,2,1]))
weight(H)  # gives  BoundsError

A quick look at the code suggests that it requires that the tableau be semistandard, but does not check this! Either we modify the code so that it checks, or we modify it so that all Young tableaux are accepted. I do also wonder whether the name should be changed to weight_sequence. I have searched quickly on internet: given a YT the weight is a sequence; it may assume that the entries in the YT are positive (or maybe just non-negative).

@ulthiel @mjrodgers Any opinion or suggestions on this?

[JohnAAbbott]

After further searching on the internet (should I believe what I find there?)... I have found a document which gives a definition of semistandard YT stating that the entries must be positive integers (a priori with no upper bound).
If we wish to adopt this definition then we must modify is_semistandard so that it checks that all entries are positive.
I wonder if the constructor young_tableau should also check that the entries are positive -- and maybe have a flag which disables this check. So far I have seen no examples where YT have non-positive entries...

[JohnAAbbott]

I also mention that the iterator semistandard_tableaux produces only YT with positive entries.

[joschmitt]

It is quite possible that there is a silent assumption in the tableaux code that any number one puts in is positive. This would also be what Fulton assumes in the book "Young Tableaux".

[JohnAAbbott]

Aha! Near the top of the [OSCAR manual page for Young tableaux]
(https://docs.oscar-system.org/stable/Combinatorics/EnumerativeCombinatorics/tableaux/#Semistandard-tableaux)

There is written "[we] assume that we fill from a set of integers from 1 up to some number"

[mjrodgers]

I have never seen any applications where the entries are allowed to be non-positive, not that I can claim to be an expert on these. I agree that a check with a flag to disable is best for efficiency.

[joschmitt]

Aha! Near the top of the [OSCAR manual page for Young tableaux] (https://docs.oscar-system.org/stable/Combinatorics/EnumerativeCombinatorics/tableaux/#Semistandard-tableaux)

There is written "[we] assume that we fill from a set of integers from 1 up to some number"

Ah, okay, good to know 😆 Then we should add some more checks in the appropriate places...

[JohnAAbbott]

At this point I suggest changing the implementation of weight so that it throws an error if any entry is non-positive, and modify the documentation to state that it works only for YT with positive entries.
I'm not sure we need to make the other changes before the Begehung... unless @joschmitt has spare time

[JohnAAbbott]

Independent comment: I do not like the way the empty partition prints out:

julia> partition([])
Int64[]

In comparison the empty Young tableau prints out specially:

julia> young_tableau(Vector{Int}[])
Empty Young tableau

[joschmitt]

Two comments from #3887:
By me:

The only function left, which still first fills an array internally and then iterates the entries, is semistandard_tableaux(shape, weight).
This function is unfortunately implemented recursively, so it would need to be reimplemented completely. There is no reference for the used algorithm given; I assume it was implemented by a Bachelor's student in JuLie originally. @ulthiel Is there a reference for this algorithm?

By @JohnAAbbott:

The doc for YTs mentions that the tableaux entries are "usually" (positive) integers in the range 1..n where n is the number of cells in the YT. This suggests two possible modifications to the UI:

• make the constructor for a YT accept only integers in the range 1..n; offer a boolean kwarg which allows positive entries from a wider range -- I have asked a few people, and no-one seemed ever to have seen non-positive entries in a YT
• insist that entries are of type Int: in ptic, disallow ZZRingElem; allowing Int8 or other "small machine integer types" seems to bring no benefit, now that iterator are genuine iterators (previously Int8 brought a minor advantage because less memory was needed for storing the full list)

What do you think about these suggestions?

[fingolfin]

I believe the original reported issues have all been either resolved, or are "by design". It is hard to be sure, though, as this discussion has meandered quite a bit and new issues were reported in comments. I just opened two separate issues for those (#4229 and #4230). If I missed anything else, please open new issues with some focus, so we don't loose sight of where we are at.