schur functions construct elements with coefficients in the wrong base ring

[videlec]

sage: Sym = SymmetricFunctions(QQ['t'])
sage: Sym.schur()([[2], [1]]) / 2
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Input In [51], in <module>
----> 1 Sym.schur()([[Integer(2)], [Integer(1)]]) / Integer(2)

File /usr/lib/python3.10/site-packages/sage/modules/with_basis/indexed_element.pyx:896, in sage.modules.with_basis.indexed_element.IndexedFreeModuleElement.__truediv__ (build/cythonized/sage/modules/with_basis/indexed_element.c:9578)()

File /usr/lib/python3.10/site-packages/sage/categories/rings.py:1349, in Rings.ElementMethods._divide_if_possible(self, y)
   1347 q, r = self.quo_rem(y)
   1348 if r != 0:
-> 1349     raise ValueError("%s is not divisible by %s"%(self, y))
   1350 return q

ValueError: 1 is not divisible by 2

The underlying reason for this error is that coefficients are stored as integers

sage: Sym.schur()([[2], [1]]).coefficients()[0].parent()
Integer Ring

Original report https://groups.google.com/g/sage-support/c/vxgtsSwJxXE

Depends on #33267

CC: @tscrim

Component: combinatorics

Author: Travis Scrimshaw

Branch: 5ffa2f0

Reviewer: Vincent Delecroix

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

[tscrim]

comment:1

Technically speaking, it shouldn’t matter that they are stored as integers as coercion should allow that to work. That being said, we can be more careful about how we build these things without a loss of optimization during the construction.

Without testing the code, I am a bit skeptical that there is not also a bug in the input because it should be a partition. I don’t quite understand why this is even constructing an element of the Schur functions, but I don’t have the code in front of me right now.

I will take a more detailed look tomorrow.

[tscrim]

comment:2

Ah, the input should be treated as a skew partition. This is where our problems comes from. Here is a more minimal example:

sage: s = SymmetricFunctions(GF(2)).s()
sage: s([[3,2,1],[2,1]])
s[1, 1, 1] + 2*s[2, 1] + s[3]
sage: s.skew_schur([[3,2,1],[2,1]])
s[1, 1, 1] + 2*s[2, 1] + s[3]

[tscrim]

Commit: 3fdf528

[tscrim]

Branch: public/combinat/skew_schur_coeff-33313

[tscrim]

comment:3

Here is a fix, where this is exposing a deeper issue with not converting the coefficients correctly. So working over, say, GF(2) leads to coefficients with 2 appearing because they were integers. Now everything is coerced into the base ring and computations are done there.

I also did some optimizations for skew_by() and _apply_multi_module_morphism(), which came up when I was looking into this ticket.

sage: s = SymmetricFunctions(QQ).s()
sage: %timeit s[5,4,2,2,1].skew_by(s[3,2,2,1] + s[3,1])
366 µs ± 2.25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

versus with #33267:

sage: %timeit s[5,4,2,2,1].skew_by(s[3,2,2,1] + s[3,1])
391 µs ± 3.62 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

versus 9.5:

sage: %timeit s[5,4,2,2,1].skew_by(s[3,2,2,1] + s[3,1])
404 µs ± 2.91 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

#33267 dependency is for a trivial conflict.

---

New commits:

6d1dbb2	Speedup of sum_of_* methods by using dictionaries directly.
7229a19	some details about shuffle of words and multizetas
ec60e55	Merge branch 'u/chapoton/33102' in 9.5
7ea8aea	fix a bug in multiple zeta values
c4415d7	Merge branch 'u/chapoton/33257' of git://trac.sagemath.org/sage into public/performance/optimize_sum_of_in_cfm-33267
fd50bb4	One additional optimization to multiple zetas.
33a7e77	Update doc of sum_of_monomials() to include iterables.
bfe5203	Fixing issues with coefficients not in the base ring for symmetric functions.
a3571ea	Optimizing the skew_by() function.
3fdf528	Micro-optimization for _apply_multi_module_morphism().

[tscrim]

Dependencies: #33267

[tscrim]

Author: Travis Scrimshaw

[videlec]

comment:4

In coerce_remove_zeros you do not apply a coercion but simply call the parent R. It would make more sense to either call it convert_remove_zeros or really use coercion val = R.coerce(D[index]).

[fchapoton]

comment:5

pyflakes plugin is not happy about the remaining

         zero = s.zero()

[sagetrac-git]

Changed commit from 3fdf528 to 5ffa2f0

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5ffa2f0

Incorporating comments from reviewers.

[tscrim]

comment:7

I have chosen to call is convert to be more flexible. I also removed the unused zero.

[tscrim]

comment:8

Patchbot is morally green (failure is due to #32773).

[videlec]

comment:9

Thanks for writing a fix.

[videlec]

Reviewer: Vincent Deleroix

[vbraun]

Changed branch from public/combinat/skew_schur_coeff-33313 to 5ffa2f0

[mkoeppe]

Changed commit from 5ffa2f0 to none

[mkoeppe]

Changed reviewer from Vincent Deleroix to Vincent Delecroix