Involutions on NSym and QSym part I

[darijgr]

This got much longer than I expected it to be because there are three "classical" involution on each of NSym and QSym and each can be computed on various bases. I ended up implementing only two of the involutions (star=rho and psi), leaving out omega (which is just a rescaled antipode) for part II.

The patch also speeds up NSym's Verschiebung on certain bases, fixes some doc, moves a reference, and changes various invocations of Composition(spam) to Compositions()(spam) for speed reasons (when spam really is just a list). Could a _Compositions (akin to _Partitions) be of use?

CC: @tscrim @sagetrac-sage-combinat @zabrocki @vbraun

Component: combinatorics

Keywords: ncsf, nsym, qsym, sage-combinat, symmetric functions, compositions

Author: Darij Grinberg

Branch/Commit: public/combinat/ncsf_qsym/involutions-15476 @ a88a476

Reviewer: Travis Scrimshaw

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

[darijgr]

comment:1

Attachment: trac_15476-NSym-QSym-invols-1-dg.patch.gz

[tscrim]

Commit: 1d9bb8f

[tscrim]

Branch: public/combinat/ncsf_qsym/involutions-15476

[tscrim]

comment:3

Hey Darij,

Here's the patch converted to a branch, along with some additional changes of mine which should net some (perhaps small) speedups (I didn't run any benchmarks, but attribute lookup is suppose to be faster than function calls). Specifically I changed Compositions()(spam) to self._basis_keys(spam) where appropriate. If you're happy with my changes, then you can set this to positive review.

Best,

Travis

---

New commits:

[1d9bb8f](https://github.com/sagemath/sagetrac-mirror/commit/1d9bb8f)	Initial review changes.
[45a791f](https://github.com/sagemath/sagetrac-mirror/commit/45a791f)	trac #15476: involutions on NSym and QSym part I

[darijgr]

comment:4

Hi Travis,

thanks a lot! I don't have git-sage running on this machine and I haven't had time to check all of your changes so far, but I can confirm that _basis_keys is the right way to go here. BUT please don't use Composition([]):

sage: %timeit S._basis_keys([])
100000 loops, best of 3: 6.38 us per loop
sage: %timeit Compositions()([])
100000 loops, best of 3: 9 us per loop
sage: %timeit Composition([])
100000 loops, best of 3: 11 us per loop

Generally, Composition(something) does some slow and dirty ducktyping and should be avoided whenever possible in code.

[tscrim]

comment:5

It's only used once and then the result is cached, and it's more readable. I don't have a strong opinion and will be happy to change it back.

[sagetrac-git]

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

[0cda84b](https://github.com/sagemath/sagetrac-mirror/commit/0cda84b)	really minor changes
[0606af3](https://github.com/sagemath/sagetrac-mirror/commit/0606af3)	Merge branch 'public/combinat/ncsf_qsym/involutions-15476' of trac.sagemath.org:sage into NSym1

[sagetrac-git]

Changed commit from 1d9bb8f to 0cda84b

[sagetrac-git]

Changed commit from 0cda84b to a88a476

[sagetrac-git]

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

[a88a476](https://github.com/sagemath/sagetrac-mirror/commit/a88a476)

ooops

[darijgr]

comment:8

If you are fine with my added changes, feel free to set this to positive.

Thanks again for reviewing this undeservedly long patch...

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:9

Looks good to me.