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.

Depends on #25133
Depends on #25136
Depends on #25141

CC: @darijgr @tscrim @zabrocki @saliola @alauve

Component: combinatorics

Keywords: IMA coding sprint, CHAs

Author: Darij Grinberg

Branch/Commit: e13a0ce

Reviewer: Mike Zabrocki

Issue created by migration from https://trac.sagemath.org/ticket/25151

[amypang]

comment:4

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

[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

[darijgr]

Branch: public/ticket/25151

[darijgr]

Author: Darij Grinberg

[darijgr]

Commit: 3211549

[sagetrac-git]

Changed commit from 3211549 to 20abbfe

[sagetrac-git]

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

20abbfe

strong refinement order on ordered set partitions

[sagetrac-git]

Changed commit from 20abbfe to 567ee7c

[sagetrac-git]

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

567ee7c

Q basis: rudimentary implementation

[sagetrac-git]

Changed commit from 567ee7c to e089f94

[sagetrac-git]

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

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

[sagetrac-git]

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

7450608

Phi basis: rudimentary implementation

[sagetrac-git]

Changed commit from e089f94 to 7450608

[darijgr]

comment:10

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.

[sagetrac-git]

Changed commit from 7450608 to 29c9278

[sagetrac-git]

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

29c9278

corrections

[sagetrac-git]

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

20331d3

Q basis: overload coproduct on Q basis for speed

[sagetrac-git]

Changed commit from 29c9278 to 20331d3

[amypang]

comment:13

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

[darijgr]

comment:14

That would be great!

[amypang]

comment:15

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.

[zabrocki]

Reviewer: Mike Zabrocki

[sagetrac-git]

Changed commit from ffb2268 to f82bb95

[sagetrac-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]

comment:33

Essentially a trivial rebase over #25141.

[tscrim]

Changed dependencies from #25133, #25136 to #25133, #25136, #25141

[sagetrac-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)

[sagetrac-git]

Changed commit from f82bb95 to fcda701

[darijgr]

comment:37

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

[kiwifb]

comment:38

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

[sagetrac-git]

Changed commit from fcda701 to e13a0ce

[sagetrac-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]

comment:40

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

[vbraun]

Changed branch from public/ticket/25151 to e13a0ce