Opened 4 years ago
Closed 4 years ago
#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, GitHub, GitLab) | Commit: | e13a0ce1ef53a73cfdef4149d16dd97bb258e545 |
Dependencies: | #25133, #25136, #25141 | Stopgaps: |
Description (last modified by )
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 4 years ago by
- Description modified (diff)
comment:2 Changed 4 years ago by
- 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
- Description modified (diff)
comment:4 Changed 4 years ago by
- Description modified (diff)
comment:5 Changed 4 years 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_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
- 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
- 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
- Commit changed from 567ee7c1722e530b5d1179b4afc13937b303f12b to e089f94670cbce19645a9d2d4782705aee8075d0
comment:9 Changed 4 years 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 4 years ago by
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
- 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
- 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
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
That would be great!
comment:15 Changed 4 years 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 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
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
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: ↓ 19 Changed 4 years 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 24|13|5 with 79|8|6 (already shifted) and get 247913856, then should there be a bar after the "4" or not?
comment:19 in reply to: ↑ 18 Changed 4 years ago by
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 4 years 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 4 years ago by
- Status changed from new to needs_review
comment:22 Changed 4 years ago by
- Dependencies set to #25133, #25136
comment:23 Changed 4 years 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 4 years 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 4 years 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 4 years 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 4 years 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 4 years 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 4 years 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 4 years ago by
- Status changed from needs_review to positive_review
comment:31 Changed 4 years ago by
- Reviewers set to Mike Zabrocki
comment:32 Changed 4 years 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_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
- Dependencies changed from #25133, #25136 to #25133, #25136, #25141
Essentially a trivial rebase over #25141.
comment:34 Changed 4 years ago by
- Status changed from needs_review to positive_review
comment:35 Changed 4 years ago by
- Milestone changed from sage-8.2 to sage-8.3
comment:36 Changed 4 years 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_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
- 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
- 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
- Commit changed from fcda701168b798d08abce5a4cdbb911c61c48525 to e13a0ce1ef53a73cfdef4149d16dd97bb258e545
comment:40 Changed 4 years 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 4 years 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.