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

[darijgr]

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.

CC: @AndrewAtLarge @mwhansen @tscrim @sagetrac-sage-combinat

Component: combinatorics

Keywords: permutation, sage-combinat, descent algebra, symmetric group, seminormal form

Author: Darij Grinberg

Branch/Commit: 78dbab4

Reviewer: Travis Scrimshaw

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

[sagetrac-git]

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

f473aba	Merge branch 'develop' into seminormal
b10ff56	Merge branch 'develop' into seminormal
ee5ceb3	descent algebra docstring now also gives a dictionary to Schocker's paper
c14f290	retracts on permutations, and corrections to my seminormal doc
a445cfe	retracts now also on symmetric group algebra

[sagetrac-git]

Changed commit from e8b22ee to a445cfe

[darijgr]

comment:3

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).

[sagetrac-git]

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

a341b68	Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into public/combinat/seminormal-15650
86963bd	Some more misc tweaks.

[sagetrac-git]

Changed commit from a445cfe to 86963bd

[tscrim]

comment:6

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.

[sagetrac-git]

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 non-empty)
c5d2a56	Merge branch 'develop' into seminormal
95cc529	Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into seminormal
cc05d00	simpler way to compute jucys-murphy elements of the hecke algebra

[sagetrac-git]

Changed commit from 86963bd to cc05d00

[darijgr]

comment:8

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

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

[darijgr]

comment:9

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).

[sagetrac-git]

Changed commit from cc05d00 to c911c71

[sagetrac-git]

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

c911c71

faster way to compute Jucys-Murphy elements in Hecke algebra

[darijgr]

comment:11

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

[sagetrac-git]

Changed commit from c911c71 to 66b7d9a

[sagetrac-git]

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

f10fe22	More review changes.
66b7d9a	Some more tweaks and added a reference for seminormal representations.

[sagetrac-git]

Changed commit from 66b7d9a to 0ea3b73

[sagetrac-git]

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

0ea3b73

Wrong formatting for docstring.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:14

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....

[darijgr]

comment:15

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.

[AndrewMathas]

comment:16

Replying to @darijgr:

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

[sagetrac-git]

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

0ee8502	Merge branch 'public/combinat/seminormal' of trac.sagemath.org:sage into seminew
d4a9857	final doc changes

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

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

[sagetrac-git]

Changed commit from ef1e722 to 4738537

[darijgr]

comment:24

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?

[AndrewMathas]

comment:25

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

[darijgr]

comment:26

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.

[tscrim]

comment:27

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?

[darijgr]

comment:29

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.)

[vbraun]

comment:30

Documentation doesn't build

[sagetrac-git]

Changed commit from 4738537 to b92a6e1

[sagetrac-git]

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

b92a6e1

non-ascii crap removed from doc

[darijgr]

comment:32

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

[sagetrac-git]

Changed commit from b92a6e1 to 78dbab4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

78dbab4

and another doc bug

[vbraun]

Changed branch from public/combinat/seminormal to 78dbab4