#25326 closed enhancement (fixed)

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

Reported by: gh-darijgr Owned by:
Priority: major Milestone: sage-8.3
Component: combinatorics Keywords: combinatorial hopf algebras, sage-combinat, WQSym
Cc: sage-combinat, 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 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.

Change History (29)

comment:1 Changed 16 months ago by gh-darijgr

  • Dependencies #25149 deleted
  • Description modified (diff)

comment:2 Changed 16 months ago by gh-darijgr

  • Authors set to Darij Grinberg
  • Branch set to public/ticket/25326
  • Commit set to 6c2eca61677c166e122961ba3ce743167f53267c
  • Keywords WQSym added

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:

8090ac8reversal and complement on ordered set partitions
df2edfdalgebraic complement on WQSym
63181f9coalgebraic complement on WQSym
3027028star involution on WQSym
6c2eca6trivial pyflakes change
Last edited 16 months ago by gh-darijgr (previous) (diff)

comment:3 Changed 16 months ago by git

  • Commit changed from 6c2eca61677c166e122961ba3ce743167f53267c to a2abc343a6cdbd4dc35d82548e7b6f915ced57ff

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

a2abc34another commutative diagram for star_involution

comment:4 Changed 16 months ago by git

  • Commit changed from a2abc343a6cdbd4dc35d82548e7b6f915ced57ff to 405071d81764afe0acc6aaace2338e87092979e0

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

405071dfix coercion bug and override methods on X, Phi and Q bases

comment:5 Changed 16 months ago by gh-darijgr

  • Description modified (diff)

comment:6 Changed 16 months ago by git

  • Commit changed from 405071d81764afe0acc6aaace2338e87092979e0 to 74696636ea96deab557aa62c146015781f380635

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

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

comment:7 Changed 16 months ago by git

  • Commit changed from 74696636ea96deab557aa62c146015781f380635 to f0642c4dc4e032573a2cf42e15cbb6d138807d48

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

f0642c4fix doc typo

comment:8 Changed 16 months ago by git

  • Commit changed from f0642c4dc4e032573a2cf42e15cbb6d138807d48 to 7927f38de3d3d57dd56600c38e69f3f8cee00886

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

7927f38override FQSym's star_involution on Monomial basis

comment:9 Changed 16 months ago by git

  • Commit changed from 7927f38de3d3d57dd56600c38e69f3f8cee00886 to 2412751e81f2b70551efb9023344b0cb5e2c8dae

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

2412751optimizations (thanks Travis)

comment:10 Changed 16 months ago by git

  • Commit changed from 2412751e81f2b70551efb9023344b0cb5e2c8dae to 00be42ca9c8ccb894b469324936a4c2146c02c29

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

00be42cmore doctests for FQSym dendriform structure

comment:11 Changed 15 months ago by git

  • Commit changed from 00be42ca9c8ccb894b469324936a4c2146c02c29 to 03b394586819615a9eb63d73eed4444d0e1ace75

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

3d31ecbfuck
03b3945faster _M_to_F_on_basis for FQSym

comment:12 Changed 15 months ago by git

  • Commit changed from 03b394586819615a9eb63d73eed4444d0e1ace75 to 5cc7747cbfead8b6fed9b16badbf5ce76f7e41a6

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

5cc7747faster _M_to_F_on_basis for FQSym

comment:13 Changed 15 months ago by 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

comment:14 Changed 15 months ago by git

  • Commit changed from 5cc7747cbfead8b6fed9b16badbf5ce76f7e41a6 to c5edf7a0b5a1d35fca70ebcb89f3d64a1ea41859

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

c5edf7afurther optimization on FQSym

comment:15 Changed 15 months ago by git

  • Commit changed from c5edf7a0b5a1d35fca70ebcb89f3d64a1ea41859 to a418d6969ab3c793f96db58a5192f35b5fccc6aa

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

a418d69document M-to-F algorithm

comment:16 Changed 15 months ago by gh-darijgr

  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from Schützenberger anti-automorphisms for WQSym, FQSym, FSym to Schützenberger anti-automorphisms for WQSym and FQSym; fleshing out FQSym

comment:17 Changed 15 months ago by git

  • Commit changed from a418d6969ab3c793f96db58a5192f35b5fccc6aa to 4312c7217bba52ffb38db343a3457f340f65670b

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

e6d34a0Merge branch 'public/ticket/25326' of git://trac.sagemath.org/sage into public/ticket/25326
4312c72Proper fix for coercion bug. Marking tests as long.

comment:18 Changed 15 months ago by git

  • Commit changed from 4312c7217bba52ffb38db343a3457f340f65670b to ebdc81750f4d7c0d28eaa47a99e51e8307342daa

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

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

comment:19 Changed 15 months ago by tscrim

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

Last edited 15 months ago by tscrim (previous) (diff)

comment:20 Changed 15 months ago by gh-darijgr

Thanks, Travis!

comment:21 Changed 15 months ago by git

  • Commit changed from ebdc81750f4d7c0d28eaa47a99e51e8307342daa to 2d9259a0ace7e631a111fa8110efcb32be01fafc

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

2d9259aSome last fixes.

comment:22 Changed 15 months ago by 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.

comment:23 Changed 15 months ago by git

  • Commit changed from 2d9259a0ace7e631a111fa8110efcb32be01fafc to 4d071302cd0f6de49b97f757027eaabeb1d14639

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

4d07130Tweaks from talking with Darij.

comment:24 Changed 15 months ago by git

  • Commit changed from 4d071302cd0f6de49b97f757027eaabeb1d14639 to 6517a1c0c741bbfb526848a60dc120bb1feee80b

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

6517a1cTweaks from talking with Darij.

comment:25 Changed 15 months ago by git

  • Commit changed from 6517a1c0c741bbfb526848a60dc120bb1feee80b to ea86580d33a64fb979b177200d5966f099c3662b

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

ea86580Tweaks from talking with Darij.

comment:26 Changed 15 months ago by git

  • Commit changed from ea86580d33a64fb979b177200d5966f099c3662b to 5e768bde77319830883074199cf1d524932e041e

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

5e768bdTweaks from talking with Darij.

comment:27 Changed 15 months ago by git

  • Commit changed from 5e768bde77319830883074199cf1d524932e041e to a4da76f5fb828f389dbb0e68905ba739ff035dec

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

a4da76fTweaks from talking with Darij.

comment:28 Changed 15 months ago by gh-darijgr

  • Status changed from needs_review to positive_review

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

comment:29 Changed 15 months ago by vbraun

  • Branch changed from public/ticket/25326 to a4da76f5fb828f389dbb0e68905ba739ff035dec
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.