Opened 5 years ago

Closed 2 months ago

#23443 closed defect (fixed)

More Schubert polynomial shenanigans

Reported by: darij Owned by:
Priority: major Milestone: sage-9.7
Component: combinatorics Keywords: schubert, polynomials, divided differences
Cc: tscrim, sage-combinat, aschilling, VivianePons Merged in:
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 94d9d75 (Commits, GitHub, GitLab) Commit: 94d9d75d07444fac858d9954992ccc89e6bcb349
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

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.

Attachments (1)

schubert-1.diff (2.9 KB) - added by gh-darijgr 4 months ago.
Fixing X([]) misbehaving and X([1]).expand() not properly coercing

Download all attachments as: .zip

Change History (21)

comment:1 Changed 5 years ago by darij

  • Cc VivianePons added

comment:2 Changed 5 years ago by tscrim

  • Description modified (diff)

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.

comment:3 Changed 5 years ago by darij

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.

comment:4 Changed 5 years ago by tscrim

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.

Changed 4 months ago by gh-darijgr

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

comment:5 Changed 4 months ago by gh-darijgr

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.

comment:6 Changed 4 months ago by tscrim

  • Authors set to Darij Grinberg
  • Branch set to public/combinat/schubert_shenanigans-23443
  • Commit set to 379fc130015e2b9f77a28e03c7f87312b2a7f204
  • Reviewers set to Travis Scrimshaw
  • Status changed from new to needs_review

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:

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

comment:7 Changed 4 months ago by tscrim

  • Milestone changed from sage-8.1 to sage-9.7

comment:8 Changed 4 months ago by gh-darijgr

  • Status changed from needs_review to positive_review

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!

comment:9 Changed 4 months ago by slelievre

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=....

comment:10 Changed 4 months ago by tscrim

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

comment:11 Changed 4 months ago by git

  • Commit changed from 379fc130015e2b9f77a28e03c7f87312b2a7f204 to c000c8c89ed17cde730b171ef938f0c539547478
  • Status changed from positive_review to needs_review

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

c000c8cBetter normalize permutations for Schubert polynomials

comment:12 follow-up: Changed 4 months ago by slelievre

  • Status changed from needs_review to positive_review

Same commit, now with author Darij Grinberg.

comment:13 Changed 4 months ago by gh-darijgr

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

comment:14 in reply to: ↑ 12 Changed 4 months ago by tscrim

Replying to slelievre:

Same commit, now with author Darij Grinberg.

Thank you. I appreciate it.

comment:15 Changed 3 months ago by vbraun

  • Status changed from positive_review to needs_work
[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".

comment:16 Changed 3 months ago by tscrim

Ack, :module: -> :mod:.

comment:17 Changed 2 months ago by git

  • Commit changed from c000c8c89ed17cde730b171ef938f0c539547478 to 94d9d75d07444fac858d9954992ccc89e6bcb349

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

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

comment:18 Changed 2 months ago by tscrim

  • Status changed from needs_work to positive_review

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.

comment:19 Changed 2 months ago by gh-darijgr

Thank you, Travis!

comment:20 Changed 2 months ago by vbraun

  • Branch changed from public/combinat/schubert_shenanigans-23443 to 94d9d75d07444fac858d9954992ccc89e6bcb349
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.