Descent algebra

[tscrim]

Implement Solomon's descent algebra (for type A_n-1) with the bases D (descents), B (subsets), and I (idempotents) following Garsia and Reutenauer.

---

Apply: attachment: trac_14981-descent_algebra-ts.patch

Depends on #14234

CC: @sagetrac-sage-combinat @anneschilling

Component: combinatorics

Keywords: Solomon's descent algebra

Author: Travis Scrimshaw

Reviewer: Darij Grinberg

Merged: sage-5.12.beta4

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

[darijgr]

comment:2

Could you please move the change to all.py and algebra.rst somewhere into a less busy location? I don't seem to have the diagram_algebras and vector_partition context.

[darijgr]

Attachment: trac_14981-descent_review_part_1-dg.patch.gz

[darijgr]

comment:3

I've attached a partial review patch attachment: trac_14981-descent_review_part_1-dg.patch. Please look it over. I've removed one_basis from the universal methods and added it to the D and B basis, since the version you had would give wrong answers in the D case. I believe that in the I basis, the 1 is not a basis element (but I might be wrong here).

I'll eventually return and finish the review, but first I'd prefer to see the following issue resolved:

It's way too tricky to call an element of the D basis. The usual trick people are doing works for subsets of size >= 2:

sage: D = DescentAlgebra(QQ, 4).D()
sage: D[1,3]
D{1, 3}

but this is widely agreed to be syntactic sugar. One-element sets work only if a comma is added at the end (D[4,] works, but D[4] does not), and the empty set doesn't work at all. Moreover, this syntax is unchecked (D[666,444] works just as well) and falsely suggests that it takes compositions where it really takes subsets.

Neither of D({1,3}), D(set([1,3])), D(Set([1,3])) works. The only thing that reliably works for all subsets is this:

sage: D.basis()[(1,3)]
D{1, 3}
sage: D.basis()[(1,)] 
D{1}
sage: D.basis()[()]  
D{}

But I don't think such a detour should be necessary.

Eventually there should be conversions into the symmetric group algebra and into and from NSym. The latter should be easy to do; the former is probably best done after dealing with the #14885 mess.

[tscrim]

comment:4

Hey Darij,

Here's a new version of the patch with your first review patch folded in. I've fixed the above issue with some input checks and added coercions into NSym and the sym. gp. algebra (which should be okay since it's getting permutations via descents). In the I basis, it is also indexed by compositions, so I_[n] is a basis element and is 1:

sage: I = DescentAlgebra(QQ, 5).I()
sage: for b in I.basis():
....:     if I.one() * b != b * I.one():
....:         print b
....:
sage: I.one() * I.one() == I.one()
True

Thanks for also filling out the references.

Ready for continued review.

Thanks,

Travis

PS - Be careful with hyphens when copy/pasting since often times they aren't ascii.

For patchbot:

Apply: trac_14981-descent_algebra-ts.patch

[darijgr]

comment:5

Hi Travis,

thanks for looking into this (and spotting the hyphens).

I still think the unity does not belong to the I basis, and your tests are wrong because your B-to-I and I-to-B transform methods handle the case of [n] in a special (and incorrect) way. Theorem 3.4 of the Garsia-Reutenauer paper, applied to r = [n], says that B_{[n]} is a linear combination (with nonzero coefficients) of all the I_q for q \leq_{\pi} [n] (and that means for all compositions q of n). In particular, B_{[n]} (which is the 1) is not a single basis element unless n \leq 1.

Care to add an empty-set check in the doctest of __getitem__? I think it would be better to explain this nonstandard syntax (D[3,4] instead of D([3,4])) in a more visible docstring, too.

I hate to say this but your patch is still getting rejected due to the all.py and algebra.rst insertion points. IMHO this is a weakness of hg (or the way we are using it), since it shouldn't actually matter where things are inserted in these two files; but for now, in order maybe you could move your insertions into some place where there has been no conflicting patch activity lately? Sorry for this stupid issue.

Best regards,

Darij

[tscrim]

comment:6

Hey Darij,

Ack, you're right about the 1, that's a big bug on my part. Fixed now. I also put a docstring at the class level about the __getitem__ (but this syntax is also used in symmetric functions) and included the emptyset test. However there's nothing I can do about the rejects because the algebra.rst should be in alphabetical order and #14234 is already positively reviewed, but that should definitely be a dependency. (I agree with you though on this shortcomming of Mercurial as Git is more robust from my experience, and the switch should happen [relatively] soon.)

Thanks,

Travis

[tscrim]

Reviewer: Darij Grinberg

[tscrim]

Dependencies: #14234

[tscrim]

comment:7

For patchbot:

Apply: trac_14981-descent_algebra-ts.patch

[darijgr]

review patch (final)

[darijgr]

comment:8

Attachment: trac_14981-review-dg.patch.gz

Hey Travis,

good work. My new review patch consists of nitpicks, basically. If you agree with it, mark this positive-review.

Best regards,

Darij

[tscrim]

comment:9

Hey Darij,

Here's with a few other changes and nitpicks on your nitpicks. Most notably I removed the citations to GR1989 since the paper was being referenced so frequently. IMO, it's at the class level, so it essentially covers all methods. If you're happy with my changes, feel free to set this to positive review.

Thanks,

Travis

[tscrim]

comment:10

For patchbot:

Apply: trac_14981-descent_algebra-ts.patch

[darijgr]

comment:11

I do think the references are useful, since they say that the notations used in the doc are identical with the notations used in [GR1989]. Of course, you can write exactly this into the docstring on the class level, but that would be a promise that all future changes to the code will still respect [GR1989] notations; I'm not sure if I could make such a promise...

Also, some details are off. First, there is no need to require R to be a QQ-algebra universally; only the I-basis needs that, and as far as I understand it is a leaf of the coercion graph. The use of < for the refinement order needs to be changed to \leq every time it appears, and you might want to point out which way it goes (I don't know if this is standard; this is the reason why I haven't used a symbol for it).

Why did you remove the paragraph about the nonstandard syntax for the D-basis? Things like this confuse me a lot when I try to use a basis.

[tscrim]

comment:12

Attachment: trac_14981-descent_algebra-ts.patch.gz

I stated explicitly that we're following [GR1989] in the class doc and changed the QQ-algebra requirement. For the refinement order, I don't think there is any ambiguity, but from the rest of the docstring, it must be that q <= p is q refines p. I removed the D-basis paragraph because D([1, 3]) should be standard syntax (at least following the symmetric functions and I forgot to test it for the D basis). I fixed this so that it works now.

For patchbot:

Apply: trac_14981-descent_algebra-ts.patch

[darijgr]

comment:13

Thanks for making the D(...)-syntax work! The rest is also fine now. Positive review!

[tscrim]

comment:14

Thanks for reviewing this patch Darij.

[jdemeyer]

Merged: sage-5.12.beta4