#25151 closed enhancement (fixed)

Implement Q-basis and fundamental basis of WQSym

Reported by: amypang Owned by:
Priority: major Milestone: sage-8.3
Component: combinatorics Keywords: IMA coding sprint, CHAs
Cc: darij, tscrim, zabrocki, saliola, alauve Merged in:
Authors: Darij Grinberg Reviewers: Mike Zabrocki
Report Upstream: N/A Work issues:
Branch: e13a0ce (Commits) Commit: e13a0ce1ef53a73cfdef4149d16dd97bb258e545
Dependencies: #25133, #25136, #25141 Stopgaps:

Description (last modified by amypang)

Please implement

-the Q basis, as in Bergeron-Zabrocki ​https://arxiv.org/abs/math/0509265 start of section 6

-the Phi basis, as in Novelli-Thibon ​https://arxiv.org/abs/math/0605061 lines 55-56

Define an order on ordered-set-partitions: u<v if v can be obtained by merging adjacent parts of u, where all numbers in the left part are smaller than all numbers in the right part.

Q_u is the sum of M_w over all w>u; Phi_v is the sum of M_w over all w<v.

Change History (41)

comment:1 Changed 17 months ago by amypang

  • Description modified (diff)
Last edited 17 months ago by amypang (previous) (diff)

comment:2 Changed 17 months ago by amypang

  • Description modified (diff)
  • Summary changed from Implement Q-basis of WQSym to Implement Q-basis and fundamental basis of WQSym

comment:3 Changed 17 months ago by amypang

  • Description modified (diff)

comment:4 Changed 17 months ago by amypang

  • Description modified (diff)

I'll keep trying to code something but I think realistically this is beyond me.

comment:5 Changed 17 months ago by gh-darijgr

  • Authors set to Darij Grinberg
  • Branch set to public/ticket/25151
  • Commit set to 3211549355bf3d154401b16fa2fd563d4953030f

Last 10 new commits:

70ccf5fchanges necessitated by renaming in #25133
e79d2d3Merge branch 'public/combinat/fqsym' of trac.sagemath.org:sage into fq2
58d17adMerge branch 'public/combinat/wqsym_morphisms-25141' of trac.sagemath.org:sage into fq2
7dd85ffimplement the M basis of FQSym
2acec00Merge branch 'WQS' into fq2
78a4253overload coproduct on M-basis for speed
ef1f3b7link FQSym doc
98fca9cMerge branch 'public/combinat/fqsym2' of trac.sagemath.org:sage into homs
416a8c0more corrections due to recent merge
3211549refinement order on ordered set partitions

comment:6 Changed 17 months ago by git

  • Commit changed from 3211549355bf3d154401b16fa2fd563d4953030f to 20abbfe0e028e6c1379f373237a5de035e97f791

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

20abbfestrong refinement order on ordered set partitions

comment:7 Changed 17 months ago by git

  • Commit changed from 20abbfe0e028e6c1379f373237a5de035e97f791 to 567ee7c1722e530b5d1179b4afc13937b303f12b

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

567ee7cQ basis: rudimentary implementation

comment:8 Changed 17 months ago by git

  • Commit changed from 567ee7c1722e530b5d1179b4afc13937b303f12b to e089f94670cbce19645a9d2d4782705aee8075d0

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

668aa69Q basis of WQSym: optimize
e089f94Phi basis: rudimentary implementation

comment:9 Changed 17 months ago by git

  • Commit changed from e089f94670cbce19645a9d2d4782705aee8075d0 to 74506086348ce4f95fdef48c830dda171e503f9c

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

7450608Phi basis: rudimentary implementation

comment:10 Changed 17 months ago by gh-darijgr

Done: both bases implemented, and product on Q-basis overloaded.

Worth doing: overload product and coproduct on Phi-basis (Novelli and Thibon give formulas for them, but they take some time to unravel), and search for a coproduct formula on Q-basis.

comment:11 Changed 17 months ago by git

  • Commit changed from 74506086348ce4f95fdef48c830dda171e503f9c to 29c9278a56e82229b9b112a0ded9f617e64daf5f

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

29c9278corrections

comment:12 Changed 17 months ago by git

  • Commit changed from 29c9278a56e82229b9b112a0ded9f617e64daf5f to 20331d343db3d250199c7d2e501fe5aa4ec9fcc4

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

20331d3Q basis: overload coproduct on Q basis for speed

comment:13 Changed 17 months ago by amypang

Ok, shall I try to understand the product and coproduct of Phi, and give that to you mathematically / pseudocode-ly?

comment:14 Changed 17 months ago by gh-darijgr

That would be great!

comment:15 Changed 17 months ago by amypang

Actually the product and coproduct on the Phi basis are quite easy to understand. But they are in terms of segmented permutations - i.e. think of the ordered set partition as a word/permutation with some bars. Because we need ideas like shuffle and deconcatenate.

  • Product = sum of shifted shuffles - i.e. compute the shifted shuffle as words, then there is a bar between letters a and b if either a,b came from the same word and there was a bar in between, or if b comes from the first word and a from the second.
  • Coproduct = deconcatenate and standardise. The deconcatenation can be within a block or between blocks.

My best idea for how to do this:

  • we already have ordered-set-partition -> composition.
  • make a function: ordered-set-partition -> permutation, that writes each block in increasing order and concatenates the blocks in the original order.
  • make an "inverse" for these combined: i.e. given a permutation and a composition, make an ordered-set-partition whose blocks have sizes given by the composition, and the first block is the first few letters of the permutation, the second block is the next few letters, and so on.

Then we can compute shuffle and deconcatenation in the permutation/composition format.

If you think it is useful, I can try to code the functions osp->permutation and (permutation,composition)->osp . But it will be of the level at #25152. Not sure if that's too rudimentary to be useful.

Sorry not to be of much help. Thanks Darij for all the coding so far.

comment:16 follow-up: Changed 17 months ago by gh-darijgr

Thank you! The coproduct (which I didn't understand due to the notation \cdot which N&T seem to have left undefined) looks easy enough to implement. The question is whether I can get the bars to work without talking about barred permutations.

comment:17 in reply to: ↑ 16 Changed 17 months ago by amypang

Replying to gh-darijgr:

Thank you! The coproduct (which I didn't understand due to the notation \cdot which N&T seem to have left undefined) looks easy enough to implement.

I think \cdot means concatenation. At least it agrees with the example on line 61.

The question is whether I can get the bars to work without talking about barred permutations.

Yeah, it might be neater/easier to make a new type of object called barred permutations (or segmented permutations, I think that's the technical term). And then for their deconcatenation, I'd imagine you would deconcatenate the permutations ignoring the bars first, and then "put the bars where they used to be" as it were. So if you think of segmented permutations as pairs (permtuation, composition), then you're deconcatenating them separately.

I don't know how to make a new type of combinatorial object like segmented permutations. Let me know if I can do anything useful.

comment:18 follow-up: Changed 17 months ago by gh-darijgr

On a second thought, the product is doable without any new objects. I'll make a helper function that turns an ordered set partition into a list by reading its blocks in increasing order, but every entry e appearing in some block will be written as (e, 1) if it was the last entry of its block and as (e, 0) otherwise. Thus, the shuffle will "remember" the bars.

HOWEVER, I am still not 100% precise on the definition. If I shuffle 24|13|5 with 79|8|6 (already shifted) and get 247913856, then should there be a bar after the "4" or not?

Last edited 17 months ago by gh-darijgr (previous) (diff)

comment:19 in reply to: ↑ 18 Changed 17 months ago by amypang

Replying to gh-darijgr:

On a second thought, the product is doable without any new objects. I'll make a helper function that turns an ordered set partition into a list by reading its blocks in increasing order, but every entry e appearing in some block will be written as (e, 1) if it was the last entry of its block and as (e, 0) otherwise. Thus, the shuffle will "remember" the bars.

This is clever. And it will do the coproduct too.

HOWEVER, I am still not 100% precise on the definition. If I shuffle 24|13|5 with 79|8|6 (already shifted) and get 247913856, then should there be a bar after the "4" or not?

I would say no bar after 4. I would say 2479|138|56. In the first term on the right hand side of line 60, there is no bar after 1.

Can we not ask Sage to check, at least in smaller examples? It can already compute products in Phi using the basis change to M's, no?

comment:20 Changed 17 months ago by git

  • Commit changed from 20331d343db3d250199c7d2e501fe5aa4ec9fcc4 to 85647e538260521b7f41bcbc212cc546fb23db92

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

85647e5Phi basis: overload product and coproduct (thanks Amy!)

comment:21 Changed 17 months ago by gh-darijgr

  • Status changed from new to needs_review

comment:22 Changed 17 months ago by gh-darijgr

  • Dependencies set to #25133, #25136

comment:23 Changed 17 months ago by git

  • Commit changed from 85647e538260521b7f41bcbc212cc546fb23db92 to 9a70368febac0e8e3007255fd943b76a5eab3ec7

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

9a70368this is no longer a todo

comment:24 Changed 17 months ago by git

  • Commit changed from 9a70368febac0e8e3007255fd943b76a5eab3ec7 to ffb226867bfecd65bb10e67ff6a0e67c60a8b2f6

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

ffb2268minor latex changes, bases should have a descriptive name and the abbreviation is a shortcut (and not the reverse)

comment:25 Changed 17 months ago by darij

Nothing wrong about that commit, but what's the purpose of the space in "W QSym"? It's not like LaTeX cares much.

comment:26 Changed 17 months ago by zabrocki

I'm happy to take it out, but try removing it... W QSym latex's fine, WQSym doesn't.

I added FQSym and WQSym to the list of combinatorial Hopf algebras.

Aaron and I were discussing about naming conventions on the way to the airport and I don't entirely remember if we came to the right conclusion: WordQuasiSymmetricFunctions/WQSym is somewhat artificial and arbitrary as a name, HopfAlgebraOfPackedWords, HopfAlgebraOfOrderedSetPartitions is not consistent. I still prefer NCQSym because the Hopf algebra is realized as the subspace of words which are invariants under shifts of the indices of the variables. We can make several entry points through a single CombinatorialHopfAlgebras entry in the global name space, but then we should add the full list.

comment:27 Changed 17 months ago by darij

I'm fine with NCQSym (I've also taken to calling its dual QCNSym), but I don't think WQSym is wrong either. Can we really rename everything without deprecation by now? We've got several tickets depending upon one another!

comment:28 Changed 17 months ago by tscrim

IMO, we don't have to deprecate if it is within release cycles. However, for something like this, if we are going to change the names, we should do so in the ticket that introduces it and percolate it up because of how fundamental it is. If it is just going to be an alias, then we can do that at anytime.

comment:29 Changed 17 months ago by zabrocki

I'm not suggesting that we change it here and now. I am only making a note on this ticket that it was discussed

comment:30 Changed 17 months ago by zabrocki

  • Status changed from needs_review to positive_review

I think that this looks really good. Nice work.

Note: related tickets on WQSym that may have minor conflicts when merged together

#25152 - implement multiplicative bases

#25155 - Implement global options for WQSym

#25141 - Homomorphisms around FQSym, WQSym

comment:31 Changed 17 months ago by zabrocki

  • Reviewers set to Mike Zabrocki

comment:32 Changed 16 months ago by git

  • Commit changed from ffb226867bfecd65bb10e67ff6a0e67c60a8b2f6 to f82bb95ed39d594a3f85a61879e91c92e005809a
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

1dfb703trivial changes
c8c6906Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms-25141
9d90234Initial additional of global options to WQSym
fd61441Added two global options for display of elements of WordQuasiSymmetricFunctions.
c828b0eSome reviewer changes.
ba70317A few more reviewer changes.
6e50492updated doc string for intended usage vis.a.vis packed words
27b9a98doctest and Travis' check
0efedd0Merge branch 'public/combinat/wqsym_options-25155' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms-25141
f82bb95Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into public/ticket/25151

comment:33 Changed 16 months ago by tscrim

  • Dependencies changed from #25133, #25136 to #25133, #25136, #25141

Essentially a trivial rebase over #25141.

comment:34 Changed 16 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:35 Changed 16 months ago by davidloeffler

  • Milestone changed from sage-8.2 to sage-8.3

comment:36 Changed 16 months ago by git

  • Commit changed from f82bb95ed39d594a3f85a61879e91c92e005809a to fcda701168b798d08abce5a4cdbb911c61c48525
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

728ff81Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms-25141
186d782Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into 25141
6735ebbfix doc of from_finite_word
4f2ddfeMerge branch 'public/combinat/fqsym2' of git://trac.sagemath.org/sage into public/combinat/fqsym2
beeea6aAbstracting methods to DRY.
6e40666Calling the M basis the monomial basis.
8dc0c5cMerge branch 'public/combinat/fqsym2' of git://trac.sagemath.org/sage into 25136
536f287Merge branch '25136' into 25141
fcda701manual merge commit (references index)

comment:37 Changed 16 months ago by gh-darijgr

  • Status changed from needs_review to positive_review

There was a conflict in reference/references/index.rst. Also I pulled in the most recent versions of the dependencies.

comment:38 Changed 15 months ago by fbissey

  • Status changed from positive_review to needs_work

Documentation is not building with this branch. You introduced a duplicate of the ber1991 reference in doc/en/reference/references/index.rst.

comment:39 Changed 15 months ago by git

  • Commit changed from fcda701168b798d08abce5a4cdbb911c61c48525 to e13a0ce1ef53a73cfdef4149d16dd97bb258e545

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

b383c8dMerge branch 'public/ticket/25151' of git://trac.sagemath.org/sage into public/ticket/25151
e13a0ceRemoving duplicate reference.

comment:40 Changed 15 months ago by tscrim

  • Status changed from needs_work to positive_review

Likely the result of a bad merge. Fixed (including verified the doc builds).

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

comment:41 Changed 15 months ago by vbraun

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