Opened 22 months ago
Closed 20 months ago
#25151 closed enhancement (fixed)
Implement Qbasis and fundamental basis of WQSym
Reported by:  amypang  Owned by:  

Priority:  major  Milestone:  sage8.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 )
Please implement
the Q basis, as in BergeronZabrocki https://arxiv.org/abs/math/0509265 start of section 6
the Phi basis, as in NovelliThibon https://arxiv.org/abs/math/0605061 lines 5556
Define an order on orderedsetpartitions: 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 22 months ago by
 Description modified (diff)
comment:2 Changed 22 months ago by
 Description modified (diff)
 Summary changed from Implement Qbasis of WQSym to Implement Qbasis and fundamental basis of WQSym
comment:3 Changed 22 months ago by
 Description modified (diff)
comment:4 Changed 22 months ago by
 Description modified (diff)
comment:5 Changed 22 months ago by
 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_morphisms25141' of trac.sagemath.org:sage into fq2

7dd85ff  implement the M basis of FQSym

2acec00  Merge branch 'WQS' into fq2

78a4253  overload coproduct on Mbasis 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 22 months ago by
 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 22 months ago by
 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 22 months ago by
 Commit changed from 567ee7c1722e530b5d1179b4afc13937b303f12b to e089f94670cbce19645a9d2d4782705aee8075d0
comment:9 Changed 22 months ago by
 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 22 months ago by
Done: both bases implemented, and product on Qbasis overloaded.
Worth doing: overload product and coproduct on Phibasis (Novelli and Thibon give formulas for them, but they take some time to unravel), and search for a coproduct formula on Qbasis.
comment:11 Changed 22 months ago by
 Commit changed from 74506086348ce4f95fdef48c830dda171e503f9c to 29c9278a56e82229b9b112a0ded9f617e64daf5f
Branch pushed to git repo; I updated commit sha1. New commits:
29c9278  corrections

comment:12 Changed 22 months ago by
 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 22 months ago by
Ok, shall I try to understand the product and coproduct of Phi, and give that to you mathematically / pseudocodely?
comment:14 Changed 22 months ago by
That would be great!
comment:15 Changed 22 months ago by
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 orderedsetpartition > composition.
 make a function: orderedsetpartition > 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 orderedsetpartition 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 followup: ↓ 17 Changed 22 months ago by
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 22 months ago by
Replying to ghdarijgr:
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 followup: ↓ 19 Changed 22 months ago by
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 24135 with 7986 (already shifted) and get 247913856, then should there be a bar after the "4" or not?
comment:19 in reply to: ↑ 18 Changed 22 months ago by
Replying to ghdarijgr:
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 24135 with 7986 (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 247913856. 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 22 months ago by
 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 22 months ago by
 Status changed from new to needs_review
comment:22 Changed 22 months ago by
 Dependencies set to #25133, #25136
comment:23 Changed 22 months ago by
 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 22 months ago by
 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 22 months ago by
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 22 months ago by
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 22 months ago by
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 22 months ago by
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 22 months ago by
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 21 months ago by
 Status changed from needs_review to positive_review
comment:31 Changed 21 months ago by
 Reviewers set to Mike Zabrocki
comment:32 Changed 21 months ago by
 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_morphisms25141' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms25141

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_options25155' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms25141

f82bb95  Merge branch 'public/combinat/wqsym_morphisms25141' of git://trac.sagemath.org/sage into public/ticket/25151

comment:33 Changed 21 months ago by
 Dependencies changed from #25133, #25136 to #25133, #25136, #25141
Essentially a trivial rebase over #25141.
comment:34 Changed 21 months ago by
 Status changed from needs_review to positive_review
comment:35 Changed 20 months ago by
 Milestone changed from sage8.2 to sage8.3
comment:36 Changed 20 months ago by
 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_morphisms25141' of git://trac.sagemath.org/sage into public/combinat/wqsym_morphisms25141

186d782  Merge branch 'public/combinat/wqsym_morphisms25141' 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 20 months ago by
 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 20 months ago by
 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 20 months ago by
 Commit changed from fcda701168b798d08abce5a4cdbb911c61c48525 to e13a0ce1ef53a73cfdef4149d16dd97bb258e545
comment:40 Changed 20 months ago by
 Status changed from needs_work to positive_review
Likely the result of a bad merge. Fixed (including verified the doc builds).
comment:41 Changed 20 months ago by
 Branch changed from public/ticket/25151 to e13a0ce1ef53a73cfdef4149d16dd97bb258e545
 Resolution set to fixed
 Status changed from positive_review to closed
I'll keep trying to code something but I think realistically this is beyond me.