More Schubert polynomial shenanigans

[darijgr]

Title stolen from Stanley, but this is, alas, a bug, not a determinant conjecture:

sage: X = SchubertPolynomialRing(ZZ)
sage: X([]).expand()
1
sage: X([1]).expand()
1
sage: X([]) == X([1])
False

Normally, X(perm) reduces the permutation perm by removing all fixed points attached to its right end (i.e., if a permutation in S_n sends n to n, then it reduces it to a permutation in S_{n-1} and so on, until this reduction is no longer possible). And rightfully so, since the Schubert basis is indexed by reduced permutations.

sage: X = SchubertPolynomialRing(ZZ)
sage: X([1])
X[1]
sage: X([1,2])
X[1]
sage: X([1,2,3])
X[1]

However, it fails to reduce [1] to [] due to the behavior of Permutation.remove_extra_fixed_points.

Can we just fix it, or does symmetrica break on contact with the empty list? In the latter case, should we reduce [] to [1] instead?

Related: #23403.

CC: @tscrim @sagetrac-sage-combinat @anneschilling @VivianePons

Component: combinatorics

Keywords: schubert, polynomials, divided differences

Author: Darij Grinberg

Branch/Commit: 94d9d75

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:2

I've updated the ticket description to better describe where the error is coming from (rather than the symptom).

There does seem to be some issue with symmetrica and empty lists:

sage: X([]) * X([1])
function: copy code: 4294967295 
python: : Numerical argument out of domain
sage: X([]) * X([])
function: copy code: 4294967295 
python: : Numerical argument out of domain

More shenanigans:

sage: it = iter(X.basis())
sage: [it.next() for _ in range(10)]
[X[],
 X[1],
 X[1, 2],
 X[2, 1],
 X[1, 2, 3],
 X[1, 3, 2],
 X[2, 1, 3],
 X[2, 3, 1],
 X[3, 1, 2],
 X[3, 2, 1]]

So one of the definite problems is that the indexing set could be considered too big. However, we could also consider X as a tower of polynomial rings, so it would make sense to distinguish X[1, 2] from X[1], etc. by considering each within a homogeneous component with a fixed number of variables.

[darijgr]

comment:3

The way I understand Schubert polynomials, you either deal with them in a fixed number of indeterminates (in which case the basis is indexed by S_n), or in infinitely many indeterminates (in which case the basis is indexed by S_0 \cup S_1 \cup S_2 \cup ..., and this is an increasing union, not a disjoint union -- i.e., we identify permutations that only differ in trailing fixed points). I have never seen a situation where Schubert polynomials have a basis indexed by the disjoint union S_0 \sqcup S_1 \sqcup S_2 \sqcup ...; they are not the Malvenuto-Reutenauer Hopf algebra. So I think the basis method is wrong here.

[tscrim]

comment:4

By doing the tower approach, you can get a little bit of both worlds: you are considering a fixed number of variables that you can arbitrarily move between different rings (i.e., you do not have to deal with coercions between different parents). I do not have any preference on what approach is taken; I am just stating how I understand the code.

However, there are some large inconsistencies between the code parts (and possibly the doc). Those do need to be fixed. We might just be better off changing the entire class to perhaps do some slight adjustments to the permutations when sending them back and forth with symmetrica.

[darijgr]

Attachment: schubert-1.diff.gz

Fixing X([]) misbehaving and X([1]).expand() not properly coercing

[darijgr]

comment:5

The attached schubert-1.diff file (I can't push for some stupid security reasons) fixes two basic bugs: the X([]) shenanigans (it's X([1]) now) and the problems stemming from X([1]).expand() landing in Z[x] instead of Z[x0] (which led to the product X([1]).expand() * X([1,2]).expand() being undefined).

The basis() method still needs to be fixed.

[tscrim]

Branch: public/combinat/schubert_shenanigans-23443

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:6

Is there anything else that is needed for this ticket? If not, then you can set a positive review if I have applied your patch correctly.

---

New commits:

379fc13

Applying Darij's patch to better normalize permutations for Schubert polynomials.

[tscrim]

Commit: 379fc13

[tscrim]

Author: Darij Grinberg

[darijgr]

comment:8

The basis still needs fixing (it has too many elements because it doesn't enforce the "no unnecessary fixed points at the end" rule for its permutation). But I'll open a new ticket for that.

Thanks for posting and reviewing, Travis!

[slel]

comment:9

Note: one can use something like

git commit --author="Other Person <other.person@example.com>

to properly indicate authorship when committing someone else's code.

Or as an afterthought, git commit --amend --no-edit --author=....

[tscrim]

comment:10

I didn't know that. Thank you. Could you push the revision? I am away from my computer until next week.

[sagetrac-git]

Changed commit from 379fc13 to c000c8c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:

c000c8c

Better normalize permutations for Schubert polynomials

[slel]

comment:12

Same commit, now with author Darij Grinberg.

[darijgr]

comment:13

Thank you! The wrong basis is now #33766, so this ticket can be closed once merged.

[tscrim]

comment:14

Replying to @slel:

Same commit, now with author Darij Grinberg.

Thank you. I appreciate it.

[vbraun]

comment:15

[sagemath_doc_html-none] [combinat ] The inventory files are in local/share/doc/sage/inventory/en/reference/combinat.
[sagemath_doc_html-none] Error building the documentation.
[sagemath_doc_html-none] Traceback (most recent call last):
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/runpy.py", line 196, in _run_module_as_main
[sagemath_doc_html-none]     return _run_code(code, main_globals, None,
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/runpy.py", line 86, in _run_code
[sagemath_doc_html-none]     exec(code, run_globals)
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage_docbuild/__main__.py", line 2, in <module>
[sagemath_doc_html-none]     main()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage_docbuild/__init__.py", line 1762, in main
[sagemath_doc_html-none]     builder()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage_docbuild/__init__.py", line 801, in _wrapper
[sagemath_doc_html-none]     getattr(DocBuilder, build_type)(self, *args, **kwds)
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage_docbuild/__init__.py", line 145, in f
[sagemath_doc_html-none]     runsphinx()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage_docbuild/sphinxbuild.py", line 326, in runsphinx
[sagemath_doc_html-none]     sys.stderr.raise_errors()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage_docbuild/sphinxbuild.py", line 262, in raise_errors
[sagemath_doc_html-none]     raise OSError(self._error)
[sagemath_doc_html-none] OSError: /home/release/Sage/local/var/lib/sage/venv-python3.10.3/lib/python3.10/site-packages/sage/combinat/permutation.py:docstring of sage.combinat.permutation.Permutation.remove_extra_fixed_points:6: ERROR: Unknown interpreted text role "module".

[tscrim]

comment:16

Ack, :module: -> :mod:.

[sagetrac-git]

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

1417ff6	Merge branch 'public/combinat/schubert_shenanigans-23443' of https://github.com/sagemath/sagetrac-mirror into public/combinat/schubert_shenanigans-23443
94d9d75	Fixing bad link in permutation.py.

[sagetrac-git]

Changed commit from c000c8c to 94d9d75

[tscrim]

comment:18

I finally was able to fix this. I checked the doc builds. Since the change is trivial, I am allowing myself to reset to a positive review.

[darijgr]

comment:19

Thank you, Travis!

[vbraun]

Changed branch from public/combinat/schubert_shenanigans-23443 to 94d9d75