Opened 4 years ago

Closed 4 years ago

# Implement Q-basis and fundamental basis of WQSym

Reported by: Owned by: amypang major sage-8.3 combinatorics IMA coding sprint, CHAs darij, tscrim, zabrocki, saliola, alauve Darij Grinberg Mike Zabrocki N/A e13a0ce e13a0ce1ef53a73cfdef4149d16dd97bb258e545 #25133, #25136, #25141

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

### comment:1 Changed 4 years ago by amypang

• Description modified (diff)
Last edited 4 years ago by amypang (previous) (diff)

### comment:2 Changed 4 years 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 4 years ago by amypang

• Description modified (diff)

### comment:4 Changed 4 years ago by amypang

• Description modified (diff)

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

### comment:5 Changed 4 years ago by gh-darijgr

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

Last 10 new commits:

 ​70ccf5f changes necessitated by renaming in #25133 ​e79d2d3 Merge branch 'public/combinat/fqsym' of trac.sagemath.org:sage into fq2 ​58d17ad Merge branch 'public/combinat/wqsym_morphisms-25141' of trac.sagemath.org:sage into fq2 ​7dd85ff implement the M basis of FQSym ​2acec00 Merge branch 'WQS' into fq2 ​78a4253 overload coproduct on M-basis for speed ​ef1f3b7 link FQSym doc ​98fca9c Merge branch 'public/combinat/fqsym2' of trac.sagemath.org:sage into homs ​416a8c0 more corrections due to recent merge ​3211549 refinement order on ordered set partitions

### comment:6 Changed 4 years ago by git

• Commit changed from 3211549355bf3d154401b16fa2fd563d4953030f to 20abbfe0e028e6c1379f373237a5de035e97f791

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

 ​20abbfe strong refinement order on ordered set partitions

### comment:7 Changed 4 years ago by git

• Commit changed from 20abbfe0e028e6c1379f373237a5de035e97f791 to 567ee7c1722e530b5d1179b4afc13937b303f12b

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

 ​567ee7c Q basis: rudimentary implementation

### comment:8 Changed 4 years ago by git

• Commit changed from 567ee7c1722e530b5d1179b4afc13937b303f12b to e089f94670cbce19645a9d2d4782705aee8075d0

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

 ​668aa69 Q basis of WQSym: optimize ​e089f94 Phi basis: rudimentary implementation

### comment:9 Changed 4 years 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:

 ​7450608 Phi basis: rudimentary implementation

### comment:10 Changed 4 years 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 4 years ago by git

• Commit changed from 74506086348ce4f95fdef48c830dda171e503f9c to 29c9278a56e82229b9b112a0ded9f617e64daf5f

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

 ​29c9278 corrections

### comment:12 Changed 4 years ago by git

• Commit changed from 29c9278a56e82229b9b112a0ded9f617e64daf5f to 20331d343db3d250199c7d2e501fe5aa4ec9fcc4

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

 ​20331d3 Q basis: overload coproduct on Q basis for speed

### comment:13 Changed 4 years 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 4 years ago by gh-darijgr

That would be great!

### comment:15 Changed 4 years 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: ↓ 17 Changed 4 years 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 4 years ago by amypang

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: ↓ 19 Changed 4 years 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 4 years ago by gh-darijgr (previous) (diff)

### comment:19 in reply to: ↑ 18 Changed 4 years ago by amypang

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 4 years ago by git

• Commit changed from 20331d343db3d250199c7d2e501fe5aa4ec9fcc4 to 85647e538260521b7f41bcbc212cc546fb23db92

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

 ​85647e5 Phi basis: overload product and coproduct (thanks Amy!)

### comment:21 Changed 4 years ago by gh-darijgr

• Status changed from new to needs_review

### comment:22 Changed 4 years ago by gh-darijgr

• Dependencies set to #25133, #25136

### comment:23 Changed 4 years ago by git

• Commit changed from 85647e538260521b7f41bcbc212cc546fb23db92 to 9a70368febac0e8e3007255fd943b76a5eab3ec7

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

 ​9a70368 this is no longer a todo

### comment:24 Changed 4 years ago by git

• Commit changed from 9a70368febac0e8e3007255fd943b76a5eab3ec7 to ffb226867bfecd65bb10e67ff6a0e67c60a8b2f6

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

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

### comment:25 Changed 4 years 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 4 years 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 4 years 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 4 years 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 4 years 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 4 years 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 4 years ago by zabrocki

• Reviewers set to Mike Zabrocki

### comment:32 Changed 4 years 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:

 ​1dfb703 trivial changes ​c8c6906 Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms-25141 ​9d90234 Initial additional of global options to WQSym ​fd61441 Added two global options for display of elements of WordQuasiSymmetricFunctions. ​c828b0e Some reviewer changes. ​ba70317 A few more reviewer changes. ​6e50492 updated doc string for intended usage vis.a.vis packed words ​27b9a98 doctest and Travis' check ​0efedd0 Merge branch 'public/combinat/wqsym_options-25155' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms-25141 ​f82bb95 Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into public/ticket/25151

### comment:33 Changed 4 years ago by tscrim

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

Essentially a trivial rebase over #25141.

### comment:34 Changed 4 years ago by tscrim

• Status changed from needs_review to positive_review

### comment:35 Changed 4 years ago by davidloeffler

• Milestone changed from sage-8.2 to sage-8.3

### comment:36 Changed 4 years 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:

 ​728ff81 Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms-25141 ​186d782 Merge branch 'public/combinat/wqsym_morphisms-25141' of git://trac.sagemath.org/sage into 25141 ​6735ebb fix doc of from_finite_word ​4f2ddfe Merge branch 'public/combinat/fqsym2' of git://trac.sagemath.org/sage into public/combinat/fqsym2 ​beeea6a Abstracting methods to DRY. ​6e40666 Calling the M basis the monomial basis. ​8dc0c5c Merge branch 'public/combinat/fqsym2' of git://trac.sagemath.org/sage into 25136 ​536f287 Merge branch '25136' into 25141 ​fcda701 manual merge commit (references index)

### comment:37 Changed 4 years 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 4 years 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 4 years ago by git

• Commit changed from fcda701168b798d08abce5a4cdbb911c61c48525 to e13a0ce1ef53a73cfdef4149d16dd97bb258e545

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

 ​b383c8d Merge branch 'public/ticket/25151' of git://trac.sagemath.org/sage into public/ticket/25151 ​e13a0ce Removing duplicate reference.

### comment:40 Changed 4 years 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 4 years ago by tscrim (previous) (diff)

### comment:41 Changed 4 years 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.