Opened 5 years ago

Closed 5 years ago

#15650 closed defect (fixed)

Permutations and symmetric group algebra: getting rid of 'mult' global in seminormal form

Reported by: darij Owned by:
Priority: major Milestone: sage-6.2
Component: combinatorics Keywords: permutation, sage-combinat, descent algebra, symmetric group, seminormal form
Cc: andrew.mathas, mhansen, tscrim, sage-combinat Merged in:
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 78dbab4 (Commits) Commit: 78dbab46b60a3a579bc27ee31fe748f7bd4575c5
Dependencies: Stopgaps:

Description (last modified by darij)

This is a sequel to #15174. The purpose of this ticket is to get rid of all uses of the PermutationOptions['mult'] global variable which determines how the product of two permutations is defined. Getting rid of the variable itself (#14885) will be tougher.

Specifically, my branch does the following:

  • All methods related to the seminormal form in sage/combinat/symmetric_group_algebra.py now no longer rely on PermutationOptions['mult']. Instead, the ones among them that used to have their result depend on 'mult' now take an optional keyword 'mult' (defaulting to l2r, not to the global setting -- not sure if this is good?).
  • The exposed seminormal-form methods now are documented. The documentation might look weird and might also be wrong at times, since my acquaintance with the seminormal form is half a day old (sorry, Andrew, for procrastinating on this!!) and since the methods were obviously written with British multiplication in mind (pq = first p then q) whereas I'm using continental multiplication (pq = first q then p). I hope someone experienced can review this, because adding wrong documentation isn't actually an improvement...
  • Descent algebra documentation has been corrected at a few points. The errors were my own and were due to me not knowing that Sage uses British multiplication. (Ceterum censeo, the continental convention is still the right one.)
  • A few minor speedups and doc improvements on the permutation code.

Change History (35)

comment:1 Changed 5 years ago by darij

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit changed from e8b22ee5eaaf6cd0a7390b4c6167e7fa9998bd60 to a445cfee2de628a9ed4f3ec5ec7c9acf048ea9e4

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

f473abaMerge branch 'develop' into seminormal
b10ff56Merge branch 'develop' into seminormal
ee5ceb3descent algebra docstring now also gives a dictionary to Schocker's paper
c14f290retracts on permutations, and corrections to my seminormal doc
a445cferetracts now also on symmetric group algebra

comment:3 Changed 5 years ago by darij

I've pushed some more changes, correcting my own doc and adding three retract maps to lower symmetric groups (I am experimenting around with them myself).

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 5 years ago by git

  • Commit changed from a445cfee2de628a9ed4f3ec5ec7c9acf048ea9e4 to 86963bdb69a80a7db937e6664ddf69f1e3272cdf

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

a341b68Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into public/combinat/seminormal-15650
86963bdSome more misc tweaks.

comment:6 Changed 5 years ago by tscrim

I've made some more tweaks which should be faster for larger n, and as well as standardized-ish (well...made into my standard) the references in permutation.py. I can't comment about the accuracy of the seminormal doc, but from my (quick) read-over it looks good. So up to that and my changes, it's a positive review from me.

comment:7 Changed 5 years ago by git

  • Commit changed from 86963bdb69a80a7db937e6664ddf69f1e3272cdf to cc05d00fa9bd6f6c4517c51ba55bb6987050f9e9

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

8a898eftaking powers of tropical zero (i.e., infinity) now possible
456e5cffurther doc fixes (really a way to tell trac that this branch is non-empty)
c5d2a56Merge branch 'develop' into seminormal
95cc529Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into seminormal
cc05d00simpler way to compute jucys-murphy elements of the hecke algebra

comment:8 Changed 5 years ago by darij

Ooops, there seems to be something wrong with my understanding of git. Manual override in progress.

Meanwhile, @Travis: thanks for your fixes; these are all good.

comment:9 Changed 5 years ago by darij

EDIT: oops, these commits here should really be removed.

Anyway, what remains to be done here is a review of the changes pertaining to the seminormal form, and of my latest commit (cc05d00).

Last edited 5 years ago by darij (previous) (diff)

comment:10 Changed 5 years ago by git

  • Commit changed from cc05d00fa9bd6f6c4517c51ba55bb6987050f9e9 to c911c71390cf51d64b270569569088ccf6d7d830

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

c911c71faster way to compute Jucys-Murphy elements in Hecke algebra

comment:11 Changed 5 years ago by darij

push --force complete, the branch should be sane now. Sorry for the mess.

comment:12 Changed 5 years ago by git

  • Commit changed from c911c71390cf51d64b270569569088ccf6d7d830 to 66b7d9accdb6adb3eb62dc11e0de32c66fa992d4

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

f10fe22More review changes.
66b7d9aSome more tweaks and added a reference for seminormal representations.

comment:13 Changed 5 years ago by git

  • Commit changed from 66b7d9accdb6adb3eb62dc11e0de32c66fa992d4 to 0ea3b7315804c95f18fa6654edbb483173674f41

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

0ea3b73Wrong formatting for docstring.

comment:14 Changed 5 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Looks good to me from the reference I found (modulo the added warning). I made some other minor tweaks, so if you're happy with my changes, then its positive review.

....unless, Andrew, we made a mistake in the seminormal doc....

comment:15 follow-up: Changed 5 years ago by darij

If you could please replace \delta_{TV} by \delta_{T,V} both times, I'd be happy (=pos_rev). (I don't want to do this right now because I'm make-docing on a different branch.)

Thanks a lot for the review! Looks like we're mostly done with the permutation order then.

Wow, did I really call the group algebra of S_5 "SGA5"? Lol, that wasn't even intended.

Last edited 5 years ago by darij (previous) (diff)

comment:16 in reply to: ↑ 15 Changed 5 years ago by andrew.mathas

Replying to darij:

If you could please replace \delta_{TV} by \delta_{T,V} both times, I'd be happy (=pos_rev). (I don't want to do this right now because I'm make-docing on a different branch.)

Thanks a lot for the review! Looks like we're mostly done with the permutation order then.

Wow, did I really call the group algebra of S_5 "SGA5"? Lol, that wasn't even intended.

I prefer \delta_{TV} myself:)

I just pulled up the documentation on seminormal representations. It doesn't seem to say very much. What did you want me to check?

Andrew

comment:17 Changed 5 years ago by git

  • Commit changed from 0ea3b7315804c95f18fa6654edbb483173674f41 to d4a9857507537761d8430c5be7fd5e6af4e4500d

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

0ee8502Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into seminew
d4a9857final doc changes

comment:18 Changed 5 years ago by darij

I've just made my change and a couple more (all cosmetic). I don't like notations which break if some variables are more than a character long...

If you could check whether the way the seminormal-basis-related methods currently are effected by the mult variable is sane (in particular, has anything to do with the way this is done in literature), I'd be very thankful. I'm leaving the patch as needs-review for this reason; if you have no comment, I'll make it positive-review. Thanks a lot!

comment:19 Changed 5 years ago by git

  • Commit changed from d4a9857507537761d8430c5be7fd5e6af4e4500d to ef1e722762b524e04a80a869d50076ab43bb6289

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

ef1e722fix doc typo

comment:20 Changed 5 years ago by darij

Any comments, Andrew?

comment:21 Changed 5 years ago by andrew.mathas

@darij Sorry, I haven't looked at this (or your query on MO), and I doubt that I will have time to do this any time soon.

I just tried reading quickly through the latest patch but I didn't see anything related to how the mult variable interacts with the seminormal form. All I noticed was the unusual choice of reference:) My guess is that if I looked at this code properly then I'd probably want to rewrite it from scratch as I seem to remember that the seminormal form code in sage is far more computationally intensive than it needs to be (working with the seminormal form is very different from working with the primitive idempotents whereas last time I looked at this code it confused these two problems).

If everyone else is happy with the changes then I suggest you just give it a positive review rather than waiting for me to have time to look at it properly.

comment:22 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

Well, the seminormal basis probably should be implemented as a proper parent class anyways. So on the basis of your comment, I'm going to give this a positive review. Thanks Andrew.

comment:23 Changed 5 years ago by git

  • Commit changed from ef1e722762b524e04a80a869d50076ab43bb6289 to 473853757fce07a9b6ee497f2821e7161ed8989c
  • 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:

d00de75Merge branch 'public/combinat/seminormal' of git://trac.sagemath.org/sage into seminor-new
4738537more doctests and one less typo

comment:24 Changed 5 years ago by darij

Oops, I just started fixing the doc. Anyway, Travis, can you look at the last couple edits? I hope the doctests will come handy when the method is improved. Thanks a lot!

Andrew, do you think the YJM element formulae provide a quicker way to the seminormals? I could implement those right away.

EDIT: Travis: why as its own class?

Last edited 5 years ago by darij (previous) (diff)

comment:25 Changed 5 years ago by andrew.mathas

Hi Darij,

To work with the seminormal form you don't need to compute the idempotents at all. Rather you just need a basis { v_t } together with an implementation of the action

s_r v_t = 1/\rho_r(t)v_t + (1+\rho_r(t))/\rho_r(t) v_{s_r t},

where \pho_r(t)=c_{r+1}(t)-c_r(t) is the axial distance from r to r+1 inside the tableau t. Here I use the convention that v_{s_r t}=0 if s_rt is not standard.

Of course, there are many other equivalent ways to write down the seminormal form, but this is my favourite version because it is very symmetric and it is defined over the rationals.

The action of the idempotents on this basis of the semisimple Specht is easy: F_s v_t=\delta_[st} v_t This follows because L_r v_t = c_r(t)v_t, for all r.

It is only when you need to work with the idempotents F_t, given explicitly as elements of the group algebra, that you ever need to use these formulas.

Andrew

comment:26 Changed 5 years ago by darij

Oh! But I meant the seminormal form for the group algebra. What you're talking is the seminormal form for its representations. IIRC Tom Denton was working on the latter when I was in Toronto two weeks ago; you might want to talk to him.

comment:27 Changed 5 years ago by tscrim

Hey Darij,

Your changes LGTM.

We'd want it's own class so it can be a proper parent. Thus we could do coercions and multiplications with that basis. Think like how Sym works, but perhaps we wouldn't use the multiple realizations framework since there is a natural basis (IMO, but I'm not anywhere close an expert in this field).

Perhaps we should open up a follow-up ticket which does that, and follow Andrew's favorite construction?

To both, do you think there is any more work to be done here?

comment:28 Changed 5 years ago by darij

  • Status changed from needs_review to positive_review

comment:29 Changed 5 years ago by darij

Thank you a lot, Travis!

I guess there are now two things to do:

  • a parent for the seminormal basis of QSn, and
  • an implementation of the seminormal basis of a single QSn-module.

We might want to open two separate tickets... (Tom Denton should be cc'ed on the second.)

comment:30 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Documentation doesn't build

comment:31 Changed 5 years ago by git

  • Commit changed from 473853757fce07a9b6ee497f2821e7161ed8989c to b92a6e1f3ff1abca66a04939e3132aa13fb05318

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

b92a6e1non-ascii crap removed from doc

comment:32 Changed 5 years ago by darij

  • Status changed from needs_work to positive_review

A reference had a hyphen instead of a dash; sorry for that. Fixed!

comment:33 Changed 5 years ago by git

  • Commit changed from b92a6e1f3ff1abca66a04939e3132aa13fb05318 to 78dbab46b60a3a579bc27ee31fe748f7bd4575c5
  • 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:

78dbab4and another doc bug

comment:34 Changed 5 years ago by darij

  • Status changed from needs_review to positive_review

comment:35 Changed 5 years ago by vbraun

  • Branch changed from public/combinat/seminormal to 78dbab46b60a3a579bc27ee31fe748f7bd4575c5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.