Opened 6 years ago
Closed 6 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:  sage6.2 
Component:  combinatorics  Keywords:  permutation, sagecombinat, descent algebra, symmetric group, seminormal form 
Cc:  andrew.mathas, mhansen, tscrim, sagecombinat  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 )
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 onPermutationOptions['mult']
. Instead, the ones among them that used to have their result depend on'mult'
now take an optional keyword'mult'
(defaulting tol2r
, not to the global setting  not sure if this is good?).
 The exposed seminormalform 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
= firstp
thenq
) whereas I'm using continental multiplication (pq
= firstq
thenp
). 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 6 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit changed from e8b22ee5eaaf6cd0a7390b4c6167e7fa9998bd60 to a445cfee2de628a9ed4f3ec5ec7c9acf048ea9e4
comment:3 Changed 6 years ago by
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 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 6 years ago by
 Commit changed from a445cfee2de628a9ed4f3ec5ec7c9acf048ea9e4 to 86963bdb69a80a7db937e6664ddf69f1e3272cdf
comment:6 Changed 6 years ago by
I've made some more tweaks which should be faster for larger n
, and as well as standardizedish (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) readover it looks good. So up to that and my changes, it's a positive review from me.
comment:7 Changed 6 years ago by
 Commit changed from 86963bdb69a80a7db937e6664ddf69f1e3272cdf to cc05d00fa9bd6f6c4517c51ba55bb6987050f9e9
Branch pushed to git repo; I updated commit sha1. New commits:
8a898ef  taking powers of tropical zero (i.e., infinity) now possible

456e5cf  further doc fixes (really a way to tell trac that this branch is nonempty)

c5d2a56  Merge branch 'develop' into seminormal

95cc529  Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into seminormal

cc05d00  simpler way to compute jucysmurphy elements of the hecke algebra

comment:8 Changed 6 years ago by
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 6 years ago by
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).
comment:10 Changed 6 years ago by
 Commit changed from cc05d00fa9bd6f6c4517c51ba55bb6987050f9e9 to c911c71390cf51d64b270569569088ccf6d7d830
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c911c71  faster way to compute JucysMurphy elements in Hecke algebra

comment:11 Changed 6 years ago by
push force complete, the branch should be sane now. Sorry for the mess.
comment:12 Changed 6 years ago by
 Commit changed from c911c71390cf51d64b270569569088ccf6d7d830 to 66b7d9accdb6adb3eb62dc11e0de32c66fa992d4
comment:13 Changed 6 years ago by
 Commit changed from 66b7d9accdb6adb3eb62dc11e0de32c66fa992d4 to 0ea3b7315804c95f18fa6654edbb483173674f41
Branch pushed to git repo; I updated commit sha1. New commits:
0ea3b73  Wrong formatting for docstring.

comment:14 Changed 6 years ago by
 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 followup: ↓ 16 Changed 6 years ago by
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 makedocing 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.
comment:16 in reply to: ↑ 15 Changed 6 years ago by
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 makedocing 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 6 years ago by
 Commit changed from 0ea3b7315804c95f18fa6654edbb483173674f41 to d4a9857507537761d8430c5be7fd5e6af4e4500d
comment:18 Changed 6 years ago by
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 seminormalbasisrelated 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 needsreview for this reason; if you have no comment, I'll make it positivereview. Thanks a lot!
comment:19 Changed 6 years ago by
 Commit changed from d4a9857507537761d8430c5be7fd5e6af4e4500d to ef1e722762b524e04a80a869d50076ab43bb6289
Branch pushed to git repo; I updated commit sha1. New commits:
ef1e722  fix doc typo

comment:20 Changed 6 years ago by
Any comments, Andrew?
comment:21 Changed 6 years ago by
@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 6 years ago by
 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 6 years ago by
 Commit changed from ef1e722762b524e04a80a869d50076ab43bb6289 to 473853757fce07a9b6ee497f2821e7161ed8989c
 Status changed from positive_review to needs_review
comment:24 Changed 6 years ago by
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?
comment:25 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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 followup 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 6 years ago by
 Status changed from needs_review to positive_review
comment:29 Changed 6 years ago by
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 QSnmodule.
We might want to open two separate tickets... (Tom Denton should be cc'ed on the second.)
comment:30 Changed 6 years ago by
 Status changed from positive_review to needs_work
Documentation doesn't build
comment:31 Changed 6 years ago by
 Commit changed from 473853757fce07a9b6ee497f2821e7161ed8989c to b92a6e1f3ff1abca66a04939e3132aa13fb05318
Branch pushed to git repo; I updated commit sha1. New commits:
b92a6e1  nonascii crap removed from doc

comment:32 Changed 6 years ago by
 Status changed from needs_work to positive_review
A reference had a hyphen instead of a dash; sorry for that. Fixed!
comment:33 Changed 6 years ago by
 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:
78dbab4  and another doc bug

comment:34 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:35 Changed 6 years ago by
 Branch changed from public/combinat/seminormal to 78dbab46b60a3a579bc27ee31fe748f7bd4575c5
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Merge branch 'develop' into seminormal
Merge branch 'develop' into seminormal
descent algebra docstring now also gives a dictionary to Schocker's paper
retracts on permutations, and corrections to my seminormal doc
retracts now also on symmetric group algebra