Schützenberger anti-automorphisms for WQSym and FQSym; fleshing out FQSym

[gh-darijgr]

This ticket implements the projection of combinatorial Hopf algebras FQSym -> QSym, a more efficient transition from the M to the F basis on FQSym (using the Möbius function of the weak order on the symmetric groups), and certain involutions of the combinatorial Hopf algebras WQSym and FQSym:

On WQSym:

• The one that, in the M-basis, reverses the ordered set partition, or equivalently complements the packed word (i.e., replaces letters 1,2,...,k by k,k-1,...,1). This is an automorphism of the algebra structure and an anti-automorphism of the coalgebra structure.

• The one that, in the M-basis, complements the (elements of the blocks of the) ordered set partition, or equivalently reverts the packed word. This is an anti-automorphism of the algebra structure (which is obvious if you look at WQSym as a subring of formal power series in non-commutative variables: then it's just a restriction of the anti-automorphism that fixes each letter) and an automorphism of the coalgebra structure.

• The composition of the above two. This is best called the star involution or the Schützenberger anti-automorphism, and is an anti-automorphism of the whole Hopf algebra. Note that this involution restricts to the star_involution method of NSym. (The previous two involutions don't restrict to any linear endomorphisms of NSym at all, so we have no caselaw telling us how to call them.)

On FQSym:

The star involution above restricts to FQSym. Also, there are two new involutions on FQSym, one of which corresponds to reversal, and the other to complement; which one depends on the basis. These are NOT restrictions of the analogous involutions of WQSym!

A later ticket, #25541, will implement similar involutions on FSym.

[gh-darijgr]

WQSym part has been implemented, at least on the M basis. I have formulas for all other basis except for C, but I haven't overridden the method so far, to avoid duplicating documentation. (I'm not actually sure if the overrides will significantly speed up the computation, except for the star involution -- since the other two involutions don't involve cancellations when you go through the M basis.)

---

New commits:

​8090ac8	reversal and complement on ordered set partitions
​df2edfd	algebraic complement on WQSym
​63181f9	coalgebraic complement on WQSym
​3027028	star involution on WQSym
​6c2eca6	trivial pyflakes change

[git]

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

​a2abc34

another commutative diagram for star_involution

[git]

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

​405071d

fix coercion bug and override methods on X, Phi and Q bases

[git]

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

​31b2e18	FQSym: add M to shortcuts
​7469663	add three involutions on FQSym, as well as FQSym -> QSym projection

[git]

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

​f0642c4

fix doc typo

[git]

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

​7927f38

override FQSym's star_involution on Monomial basis

[git]

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

​2412751

optimizations (thanks Travis)

[git]

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

​00be42c

more doctests for FQSym dendriform structure

[git]

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

​3d31ecb	fuck
​03b3945	faster _M_to_F_on_basis for FQSym

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​5cc7747

faster _M_to_F_on_basis for FQSym

[gh-darijgr]

I've implemented an explicit M-to-F transition matrix for FQSym as well, as was suggested in one of the TODOs. This speeds up computations for all but the simplest cases (warning: these times are on Cygwin):

Before:

sage: FQSym = algebras.FQSym(ZZ); FQSym.inject_shorthands()
Defining F as shorthand for Free Quasi-symmetric functions over Integer Ring in the F basis
Defining G as shorthand for Free Quasi-symmetric functions over Integer Ring in the G basis
Defining M as shorthand for Free Quasi-symmetric functions over Integer Ring in the Monomial basis
sage: %timeit F(M[3,2,1])
10000 loops, best of 3: 88.2 µs per loop
sage: %timeit F(M[1,2,3])
1000 loops, best of 3: 489 µs per loop
sage: %timeit F(M[2,1,3])
1000 loops, best of 3: 214 µs per loop
sage: %timeit F(M[1])
The slowest run took 4.19 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 81 µs per loop
sage: %timeit F(M[1,2,3,4])
100 loops, best of 3: 2.9 ms per loop
sage: %timeit F(M[4,2,1,3])
1000 loops, best of 3: 220 µs per loop
sage: %timeit F(M[6,2,5,1,3,4])
100 loops, best of 3: 2.06 ms per loop
sage: %timeit F(M[8,3,2,1,4,5,6,7])
1 loop, best of 3: 1.66 s per loop

After:

sage: FQSym = algebras.FQSym(ZZ); FQSym.inject_shorthands()
Defining F as shorthand for Free Quasi-symmetric functions over Integer Ring in the F basis
Defining G as shorthand for Free Quasi-symmetric functions over Integer Ring in the G basis
Defining M as shorthand for Free Quasi-symmetric functions over Integer Ring in the Monomial basis
sage: %timeit F(M[3,2,1])
10000 loops, best of 3: 196 µs per loop
sage: %timeit F(M[1,2,3])
1000 loops, best of 3: 243 µs per loop
sage: %timeit F(M[2,1,3])
10000 loops, best of 3: 191 µs per loop
sage: %timeit F(M[1])
10000 loops, best of 3: 136 µs per loop
sage: %timeit F(M[1,2,3,4])
1000 loops, best of 3: 382 µs per loop
sage: %timeit F(M[4,2,1,3])
10000 loops, best of 3: 203 µs per loop
sage: %timeit F(M[6,2,5,1,3,4])
1000 loops, best of 3: 281 µs per loop
sage: %timeit F(M[8,3,2,1,4,5,6,7])
1000 loops, best of 3: 776 µs per loop

[git]

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

​c5edf7a

further optimization on FQSym

[git]

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

​a418d69

document M-to-F algorithm

[git]

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

​e6d34a0	Merge branch 'public/ticket/25326' of git://trac.sagemath.org/sage into public/ticket/25326
​4312c72	Proper fix for coercion bug. Marking tests as long.

[git]

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

​ebdc817

Shorter test for TestSuite(FQSym.M()).

[tscrim]

Frédéric, I wanted to let you know that my previous commit is a fix for the long tests on this ticket.

Also for the new test, here is the top of a %prun:

         60055285 function calls (59625813 primitive calls) in 22.503 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
 22568202    6.561    0.000    9.473    0.000 combinat.py:930(__eq__)
     6564    4.433    0.001   19.148    0.003 tools.py:20(transitive_ideal)
23590175/23590174    3.045    0.000    3.045    0.000 {isinstance}
   360076    1.124    0.000    2.176    0.000 permutation.py:483(__init__)
   180428    0.830    0.000    4.829    0.000 permutation.py:3772(permutohedron_succ)
   188037    0.577    0.000    0.882    0.000 free_module.py:1049(_monomial)
   360076    0.556    0.000    0.855    0.000 combinat.py:1256(__init__)
  2399452    0.507    0.000    0.909    0.000 combinat.py:1201(index)
   180428    0.483    0.000    1.144    0.000 permutation.py:3805(<lambda>)
  2417264    0.406    0.000    0.406    0.000 {method 'index' of 'list' objects}

So about 1/2 of the time is spent just checking that two permutations are equal.

[gh-darijgr]

Thanks, Travis!

[git]

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

​2d9259a

Some last fixes.

[tscrim]

Thinking more about the doc, I don't like the fact that the definitions are in one category file that is basically overwritten in the special cases. So the documentation is not well localized. Although one of the annoying things is it would require a fair bit of duplication. So I am inclined to let it be.

Thus, if my changes are good, then positive review.

[git]

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

​4d07130

Tweaks from talking with Darij.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​6517a1c

Tweaks from talking with Darij.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​ea86580

Tweaks from talking with Darij.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​5e768bd

Tweaks from talking with Darij.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a4da76f

Tweaks from talking with Darij.

[gh-darijgr]

Thanks, Travis! Newest version of your commit looks good.