Opened 8 years ago

Closed 8 years ago

#14981 closed enhancement (fixed)

Descent algebra

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-5.12
Component: combinatorics Keywords: Solomon's descent algebra
Cc: sage-combinat, aschilling Merged in: sage-5.12.beta4
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14234 Stopgaps:

Status badges

Description (last modified by tscrim)

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


Apply: trac_14981-descent_algebra-ts.patch

Attachments (3)

trac_14981-descent_review_part_1-dg.patch (9.5 KB) - added by darij 8 years ago.
trac_14981-review-dg.patch (8.2 KB) - added by darij 8 years ago.
review patch (final)
trac_14981-descent_algebra-ts.patch (32.6 KB) - added by tscrim 8 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 8 years ago by tscrim

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by darij

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.

Changed 8 years ago by darij

comment:3 Changed 8 years ago by darij

I've attached a partial review patch 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.

comment:4 Changed 8 years ago by tscrim

  • Description modified (diff)

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

comment:5 Changed 8 years ago by darij

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

comment:6 Changed 8 years ago by tscrim

  • Dependencies set to #14234
  • Reviewers set to Darij Grinberg

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

comment:7 Changed 8 years ago by tscrim

For patchbot:

Apply: trac_14981-descent_algebra-ts.patch

Changed 8 years ago by darij

review patch (final)

comment:8 Changed 8 years ago by darij

Hey Travis,

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

Best regards,
Darij

comment:9 Changed 8 years ago by tscrim

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

comment:10 Changed 8 years ago by tscrim

For patchbot:

Apply: trac_14981-descent_algebra-ts.patch

comment:11 Changed 8 years ago by darij

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.

Changed 8 years ago by tscrim

comment:12 Changed 8 years ago by tscrim

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

comment:13 Changed 8 years ago by darij

  • Status changed from needs_review to positive_review

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

comment:14 Changed 8 years ago by tscrim

Thanks for reviewing this patch Darij.

comment:15 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.12.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.