Opened 16 months ago
Closed 15 months ago
#25326 closed enhancement (fixed)
Schützenberger antiautomorphisms for WQSym and FQSym; fleshing out FQSym
Reported by:  ghdarijgr  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  combinatorics  Keywords:  combinatorial hopf algebras, sagecombinat, WQSym 
Cc:  sagecombinat, tscrim, darij, zabrocki, alauve, saliola, amypang, chapoton  Merged in:  
Authors:  Darij Grinberg  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  a4da76f (Commits)  Commit:  a4da76f5fb828f389dbb0e68905ba739ff035dec 
Dependencies:  Stopgaps: 
Description (last modified by )
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 Mbasis, reverses the ordered set partition, or equivalently complements the packed word (i.e., replaces letters 1,2,...,k by k,k1,...,1). This is an automorphism of the algebra structure and an antiautomorphism of the coalgebra structure.
 The one that, in the Mbasis, complements the (elements of the blocks of the) ordered set partition, or equivalently reverts the packed word. This is an antiautomorphism of the algebra structure (which is obvious if you look at WQSym as a subring of formal power series in noncommutative variables: then it's just a restriction of the antiautomorphism 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 antiautomorphism, and is an antiautomorphism 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.
Change History (29)
comment:1 Changed 16 months ago by
 Dependencies #25149 deleted
 Description modified (diff)
comment:2 Changed 16 months ago by
 Branch set to public/ticket/25326
 Commit set to 6c2eca61677c166e122961ba3ce743167f53267c
 Keywords WQSym added
comment:3 Changed 16 months ago by
 Commit changed from 6c2eca61677c166e122961ba3ce743167f53267c to a2abc343a6cdbd4dc35d82548e7b6f915ced57ff
Branch pushed to git repo; I updated commit sha1. New commits:
a2abc34  another commutative diagram for star_involution

comment:4 Changed 16 months ago by
 Commit changed from a2abc343a6cdbd4dc35d82548e7b6f915ced57ff to 405071d81764afe0acc6aaace2338e87092979e0
Branch pushed to git repo; I updated commit sha1. New commits:
405071d  fix coercion bug and override methods on X, Phi and Q bases

comment:5 Changed 16 months ago by
 Description modified (diff)
comment:6 Changed 16 months ago by
 Commit changed from 405071d81764afe0acc6aaace2338e87092979e0 to 74696636ea96deab557aa62c146015781f380635
comment:7 Changed 16 months ago by
 Commit changed from 74696636ea96deab557aa62c146015781f380635 to f0642c4dc4e032573a2cf42e15cbb6d138807d48
Branch pushed to git repo; I updated commit sha1. New commits:
f0642c4  fix doc typo

comment:8 Changed 16 months ago by
 Commit changed from f0642c4dc4e032573a2cf42e15cbb6d138807d48 to 7927f38de3d3d57dd56600c38e69f3f8cee00886
Branch pushed to git repo; I updated commit sha1. New commits:
7927f38  override FQSym's star_involution on Monomial basis

comment:9 Changed 16 months ago by
 Commit changed from 7927f38de3d3d57dd56600c38e69f3f8cee00886 to 2412751e81f2b70551efb9023344b0cb5e2c8dae
Branch pushed to git repo; I updated commit sha1. New commits:
2412751  optimizations (thanks Travis)

comment:10 Changed 16 months ago by
 Commit changed from 2412751e81f2b70551efb9023344b0cb5e2c8dae to 00be42ca9c8ccb894b469324936a4c2146c02c29
Branch pushed to git repo; I updated commit sha1. New commits:
00be42c  more doctests for FQSym dendriform structure

comment:11 Changed 15 months ago by
 Commit changed from 00be42ca9c8ccb894b469324936a4c2146c02c29 to 03b394586819615a9eb63d73eed4444d0e1ace75
comment:12 Changed 15 months ago by
 Commit changed from 03b394586819615a9eb63d73eed4444d0e1ace75 to 5cc7747cbfead8b6fed9b16badbf5ce76f7e41a6
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

comment:13 Changed 15 months ago by
I've implemented an explicit MtoF 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 Quasisymmetric functions over Integer Ring in the F basis Defining G as shorthand for Free Quasisymmetric functions over Integer Ring in the G basis Defining M as shorthand for Free Quasisymmetric 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 Quasisymmetric functions over Integer Ring in the F basis Defining G as shorthand for Free Quasisymmetric functions over Integer Ring in the G basis Defining M as shorthand for Free Quasisymmetric 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
comment:14 Changed 15 months ago by
 Commit changed from 5cc7747cbfead8b6fed9b16badbf5ce76f7e41a6 to c5edf7a0b5a1d35fca70ebcb89f3d64a1ea41859
Branch pushed to git repo; I updated commit sha1. New commits:
c5edf7a  further optimization on FQSym

comment:15 Changed 15 months ago by
 Commit changed from c5edf7a0b5a1d35fca70ebcb89f3d64a1ea41859 to a418d6969ab3c793f96db58a5192f35b5fccc6aa
Branch pushed to git repo; I updated commit sha1. New commits:
a418d69  document MtoF algorithm

comment:16 Changed 15 months ago by
 Description modified (diff)
 Status changed from new to needs_review
 Summary changed from Schützenberger antiautomorphisms for WQSym, FQSym, FSym to Schützenberger antiautomorphisms for WQSym and FQSym; fleshing out FQSym
comment:17 Changed 15 months ago by
 Commit changed from a418d6969ab3c793f96db58a5192f35b5fccc6aa to 4312c7217bba52ffb38db343a3457f340f65670b
comment:18 Changed 15 months ago by
 Commit changed from 4312c7217bba52ffb38db343a3457f340f65670b to ebdc81750f4d7c0d28eaa47a99e51e8307342daa
Branch pushed to git repo; I updated commit sha1. New commits:
ebdc817  Shorter test for TestSuite(FQSym.M()).

comment:19 Changed 15 months ago by
 Cc chapoton added
 Reviewers set to Travis Scrimshaw
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.
comment:20 Changed 15 months ago by
Thanks, Travis!
comment:21 Changed 15 months ago by
 Commit changed from ebdc81750f4d7c0d28eaa47a99e51e8307342daa to 2d9259a0ace7e631a111fa8110efcb32be01fafc
Branch pushed to git repo; I updated commit sha1. New commits:
2d9259a  Some last fixes.

comment:22 Changed 15 months ago by
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.
comment:23 Changed 15 months ago by
 Commit changed from 2d9259a0ace7e631a111fa8110efcb32be01fafc to 4d071302cd0f6de49b97f757027eaabeb1d14639
Branch pushed to git repo; I updated commit sha1. New commits:
4d07130  Tweaks from talking with Darij.

comment:24 Changed 15 months ago by
 Commit changed from 4d071302cd0f6de49b97f757027eaabeb1d14639 to 6517a1c0c741bbfb526848a60dc120bb1feee80b
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6517a1c  Tweaks from talking with Darij.

comment:25 Changed 15 months ago by
 Commit changed from 6517a1c0c741bbfb526848a60dc120bb1feee80b to ea86580d33a64fb979b177200d5966f099c3662b
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ea86580  Tweaks from talking with Darij.

comment:26 Changed 15 months ago by
 Commit changed from ea86580d33a64fb979b177200d5966f099c3662b to 5e768bde77319830883074199cf1d524932e041e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
5e768bd  Tweaks from talking with Darij.

comment:27 Changed 15 months ago by
 Commit changed from 5e768bde77319830883074199cf1d524932e041e to a4da76f5fb828f389dbb0e68905ba739ff035dec
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a4da76f  Tweaks from talking with Darij.

comment:28 Changed 15 months ago by
 Status changed from needs_review to positive_review
Thanks, Travis! Newest version of your commit looks good.
comment:29 Changed 15 months ago by
 Branch changed from public/ticket/25326 to a4da76f5fb828f389dbb0e68905ba739ff035dec
 Resolution set to fixed
 Status changed from positive_review to closed
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:
reversal and complement on ordered set partitions
algebraic complement on WQSym
coalgebraic complement on WQSym
star involution on WQSym
trivial pyflakes change