Implement Q-basis and fundamental basis of WQSym

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

[amypang]

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

[gh-darijgr]

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

[git]

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

​20abbfe

strong refinement order on ordered set partitions

[git]

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

​567ee7c

Q basis: rudimentary implementation

[git]

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

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

[git]

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

​7450608

Phi basis: rudimentary implementation

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

[git]

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

​29c9278

corrections

[git]

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

​20331d3

Q basis: overload coproduct on Q basis for speed

[amypang]

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

[gh-darijgr]

That would be great!

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

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

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

[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?

[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?

[git]

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

​85647e5

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

[git]

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

​9a70368

this is no longer a todo

[git]

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)

[darij]

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

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

[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!

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

[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

[zabrocki]

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

[git]

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

[tscrim]

Essentially a trivial rebase over #25141.

[git]

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)

[gh-darijgr]

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

[fbissey]

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

[git]

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.

[tscrim]

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