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]

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
 Implement Solomon's descent algebra (for type A<sub>n-1</sub>) with the bases D (descents), B (subsets), and I (idempotents) following Garsia and Reutenauer.
+
+---
+
+Apply: [attachment: trac_14981-descent_algebra-ts.patch](https://github.com/sagemath/sage-prod/files/10658214/trac_14981-descent_algebra-ts.patch.gz)

[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