Jucys-Murphy elements and induction

This post concerns the representation theory of the symmetric group over the complex numbers. Recall that the irreducible representations of the symmetric group S_n are indexed by partitions of n. Let S^\lambda be the irreducible representation indexed by \lambda. I want to say some words about the theorem that the decomposition of the induced module \operatorname{Ind}_{S_{n}}^{S_{n+1}}S^\lambda is given by the decomposition into eigenspaces under the action of the Jucys-Murphy element.

First, the relevant Jucys-Murphy element is

    \[X:=(1,n+1)+(2,n+1)+\cdots+(n,n+1)\in \mathbb{C}[S_{n+1}].\]

The way it acts on \operatorname{Ind}_{S_{n}}^{S_{n+1}}S^\lambda=\mathbb{C}[S_{n+1}]\otimes_{\mathbb{C}[S_n]}S^\la is not as an element of \mathbb{C}[S_{n+1}] but by X\cdot (a\otimes v)=aX\otimes v. This is well-defined since X commutes with \mathbb{C}[S_n].

What this action defines is a natural transformation from the functor \operatorname{Ind}_{S_{n}}^{S_{n+1}} to itself. The induction functor is (bi)-adjoint to the restriction functor and this natural transformation is even simpler to construct on the adjoint side. Recall that if \mathcal{F} and \mathcal{G} are adjoint functors, then there is an isomorphism

    \[\operatorname{End}\mathcal{F}\cong\operatorname{End}\mathcal{G}.\]

Here \operatorname{End}\mathcal{F} refers to the natural transformations from \mathcal{F} to itself, and the map in this isomorphism is given by pre- and post-composition by the unit and counit of the adjunction.

And the way that X yields a natural transformation from \operatorname{Res}_{S_n}^{S_{n+1}} to itself is very simple, it’s just by its usual action as an element of \mathbb{C}[S_{n+1}]. If you transport this natural transformation to a natural transformation of the induction functor via the method I just mentioned, then you get the formula mentioned above.

Now given a pair of adjoint functors \mathcal{F} and \mathcal{G}, a natural transformation X from \mathcal{F} to \mathcal{F} (and hence from \mathcal{G} to \mathcal{G}) and a complex number a, we can define a functor \mathcal{F}_a by

    \[\mathcal{F}_a(V)=\{w\in \mathcal{F}(V)\mid Xw=aw\}.\]

and similarly for \mathcal{G} (this requires some linearity assumptions, but they’re satisfied here. Also you could take generalised eigenspaces if you wanted to, but in our application there is no difference).

When you do this, the functors \mathcal{F}_a and \mathcal{G}_a are adjoint:

Proof: Both \operatorname{Hom}(\mathcal{F}_aV,W) and \operatorname{Hom}(V,\mathcal{G}_aW) are the a-eigenspace of the action of X on \operatorname{Hom}(\mathcal{F}V,W)\cong\operatorname{Hom}(V,\mathcal{G}W).

Now apply this to our situation. We also use the following standard fact about the action of the Jucys-Murphy element (as developed e.g. in the Vershik-Okounkov approach):

Consider the decomposition

    \[\operatorname{Res}_{S_n}^{S_{n+1}}S^\mu=\bigoplus_{\lambda\to\mu}S^\lambda.\]

Then the Jucys-Murphy element X acts by the scalar c(\alpha) on S^\lambda, where c(\alpha) is the content of the box \alpha added to \lambda to get \mu.

Now translating this statement via the above yoga onto the adjoint side, we get

In the decomposition

    \[\operatorname{Ind}_{S_{n}}^{S_{n+1}}S^\lambda=\bigoplus_{\lambda\to\mu}S^\mu,\]

the Jucys-Murphy element X acts by the scalar c(\alpha) on S^\mu, where c(\alpha) is the content of the box \alpha added to \lambda to get \mu.

Oaxaca Photos (December 2019)

I picked up my old phone and decided to try turning it on again. And after charging it, I was surprised, it turned on for the first time in 18 months. I guess the remedy for fixing a water damaged phone is to just wait a long long time.

This means I got access to some photos that I thought were previously lost, and I’ll present some of them here today.

Our trip begins in Oaxaca City, where I was visiting Banff in Mexico. First up, we have a visit to Monte Albán, an archaeological site on top of a hill right next to the city itself.

Next we see a scene in the city. A wedding party is marching down the street.

Now there is a picture of myself, to convince you that I actually was there.

That picture and the rest of the pictures below were all taken at Hierve El Agua.

Part 2 of Mexican photos coming soon.

Diplomacy Scoring Systems

I am going to write about scoring systems. If you want to skip ahead to the end and see a good system you can use, feel free to do so. Recall that the purpose of a scoring system is to provide a just numerical evaluation of a drawn position in a diplomacy game, for quantifying performances in a tournament.

We will start very slowly by stating some properties that diplomacy scoring systems should have.

1. Solo beats Draw beats Elimination/Loss:
A soloist should score more than someone who draws, who should in turn score more than someone who is eliminated or loses.

Comment: This sounds like an obvious property to want. Yet I feel compelled to mention this, and others explicitly, because not all scoring systems have this property. Carnage is a notorious example. (A historical note: We (by this I mean Bob Holt) fixed this problem with Carnage back in 2009. Then people reverted to the older, worse version).

2. Monotonicity:
Compare the score from two games (games are assumed drawn unless otherwise specified), where the only difference is that player A takes a centre off player B in the 2nd game. Then Player A should score more in Game 2 than in Game 1, and it should be the other way around for Player B.

Comment: Again, this sounds obvious, but does not always happen. An example of a system which doesn’t have this property is Tribute.

3. Path independence
A player’s score should only depend on the final centre count of the game.

Comment: In the past systems have been used (e.g. Origins) which use the centre count at each year in the figuring of the final scores. These produce perverse outcomes, where smaller powers can score more than larger powers. Such systems should be avoided on principle and due to their known poor performance.

Comment 2: For a further comment about survival points for eliminated or losing players, keep reading to point #5.

4. Zero Sum.
That the total points given out for each game is a constant.

Comment: There are people who belive that this should be a requirement. It sounds nice at first glance, but (spoiler alert) we will end up ditching this idea, in favour of ensuring requirements 5, 6 and 7 happen.

5. Eliminated or losing players score zero.
As it says in the title.

Comment: This is something that I would argue for in a major tournament, because to be eliminated or lose is to have achieved nothing. In a minor tournament, I am amenable to giving a token sum of survival points as seen in Detour or Cricket after hearing Melissa Call argue persuasively in its favour. An alternative approach that is irrelevant for the question of how to score a single game but relevant for a tournament is to give every player a fixed extra number of points for playing in a round.

6. Convexity/No unnatural Draw Whittling.
If Player A allows Player B to capture every supply centre of Player C, then Player A’s score should not increase.

Comment: If you reach a position which is naturally drawn, and the large players are incentivised to artificially manouver in order to ensure the smaller powers can be safely eliminated, then this causes the game to drag on longer than it should, and feels particularly nasty towards those who are eliminated late. This is essentially the standard argument against draw size based systems, although draw based scoring has other undesirable implications that I won’t get into here.

7. Reward the draw
The difference between a 1SC power in a draw must be significantly different from an elimination/loss.

Comment: I believe that there is a significant difference in achievement in making it into the draw, and that this should be rewarded by the scoring system. This is a property that is seriously lacking in some systems (Squares is a notable offender here).

8. No ties.
It is impossible to avoid ties together, but the ideal is for a system is to have as few ties at the top end of the field as possible.

Comment: If you have a simple scoring system, then you have to deal with tiebreakers. I have determined that humans are bad at coming up with tiebreaker rules. For an example, look at the farcical boundaries rule which determined the winner of the 2019 World Cup. Thus, I prefer to avoid them. Though I will mention one tiebreaker rule I read once in some tournament rules and rather fancied: “Ties will be broken by strength of opponents faced. Strength of opponents is determined by their performance in this tournament.” How exactly the strength of opponents was determined was not explicated.

9. The soloist does not win the tournament by default
A solo should be beatable by a combination of non-solo results.

Comment: This is more about tournament structure than scoring a single game so is orthogonal to most of this article, but I mention it for completeness. I believe that to do well in a tournament, you should have to do well in more than one game, rather than getting lucky in a single game (the difference between a solo and a dominant board top is often the luck of the draw in how well the defenders play).

OK enough about desirable (or undesirable) properties. And on to actually talking about some systems.

The simplest (reasonable) scoring system is 1 point per supply centre. It’s actually pretty good. Problems it comes up against are points 8 and 7 above. Still, this system is a good litmus test for any scoring system designers. I think any scoring system designer has to justify that their system is better than just counting up the dots.

A more nuanced system is one where you get a points per supply centre, b points for being in the draw, and c points are shared equally between the board-toppers. The values of a, b and c can be adjusted as desired. This is the system in use for the virtual World Diplomacy Classic running later this month. These systems can be very good.

To reduce the chance of ties, we can now make some changes. Let f(x) be an increasing convex function with f(0)=0. Suppose player i finishes with a_i supply centres. Then we give Player i the score

\displaystyle \frac{f(a_i)}{\sum_{j=1}^7 f(a_j)}.

The first system mentioned above is the same as this one with f(x)=x. It is customary to multiply scores by 100 in real life systems of this type but as that makes no mathematical difference so we ignore it.

The consequence of making the function convex is that it means that at a given supply centre count, the more evenly split your opponents are, the higher your score. It ensures that property 6 holds.

One example with a history of use in the hobby is the function f(x)=x^2 (Squares). This has two serious problems. One is that it fails property 7 (reward the draw). In this system, the score aquired by a 1 supply centre power is so small as to be essentially meaningless in any final tournament standings. The second problem is that it is too convex (to quote Nicolas Sahuget). This results in a large range of scores which a dominant board-topper can achieve. This range feels disproportionately large compared to the other scores in the sytem. But this problem is easily fixed by changing f.

We can fix the problem of failing property 7 by removing the requirement that f(0)=0, and allowing f(0) to take any postive value. Now if player i finishes with a_i supply centres, then they score as in the previous displayed formula when a_i>0, and score 0 otherwise.

Note that it is important to still include the eliminated players in the denominator, otherwise the convexity condition will be broken. This system breaks the zero-sum condition (in a fairly mild way). I strongly believe this is a small price to pay for its other desirable factors.

I hereby propose that we take f(x)=\sqrt{x^2+6x+10}. This clearly has some motivations from the Cricket scoring system, which only fails the tie-breaker condition amongst the desirable points raised above.

I have left out the question of how many points a soloist should get since it is independent of the discussion of how to score the drawn positions. I will give an explicit sample number below in my final description that agrees with my philosophy that a soloist should be able to be beaten in a (fictionally 3-round) tournament, since a tournament is meant to require playing well in multiple games, not just one.

Afficionados of lead based systems can always throw on extra bonus points for placement in a draw, though we start to lose some elegance with that approach.

So finally, we reach:

Unnamed Scoring System

Let f(x)=\sqrt{x^2+6x+10}.

For games that end in a solo, the soloist scores 0.55 points. All other players score 0.

For games that end in a draw, let a_i be the number of supply centres of player i. Then if a_i=0, player i scores 0 points, while if a_i>0, player i scores \displaystyle \frac{f(a_i)}{\sum_{j=1}^7 f(a_j)} points.

PostScripts

1. The Unnamed system is essentially 3 points for being in a draw, plus one point per supply centre, tweaked ever so slightly so that it is unlikely to create ties.

2. A comment by SK suggests that the word Carnage should be in the scoring system name.

3. Comments are not showing up, but are readable by me. I do not know why.

Running a bash process on startup in ubuntu

Ubuntu has a place called “Startup Applications Preferences” which is one way to organise something that runs upon startup. It is found by typing its name in the searchy thingy I don’t know the name of, and is a bit GUIish.

Because I use a Kinesis Advantage keyboard, I wanted to automatically swap the roles of the Tab and Delete keys upon startup. Here I record how to do this.

In the aforementioned “Startup Applications Preferences”, I create a new process, with the command section filled in with

bash .xmodstartup

It remains to create a file called .xmodstartup in my home directory, which I populate with the following xmodmap commands

xmodmap -e 'keycode 119 = Tab ISO_Left_Tab'
xmodmap -e 'keycode 23 = Delete NoSymbol'

And voila, upon startup, the Tab and Delete keys are switched.

If I ever want to undo this, and return to the default keyboard layout, this can be accomplished with running the following in a terminal

setxkbmap -layout us

This blog post exists to help my future self solve the same problem when I forget, and hopefully may help others who stumble upon it while searching the web to try and solve the same problem as me.

Now, next thing to do is to understand how to make the Windows/Super key behave exactly as I want it.

Molecube (nine colour cube)

The molecube (also known as the nine colour cube, e.g. as on Jaap’s website) is a Rubiks cube variant. Here is a picture in its scrambled state (so no spoilers are given).
molecube

To solve the puzzle you must reach a state where there there are no two pieces of the same colour on any of the six faces. In terms of turning, it is exactly like a normal Rubiks cube.

It is not too difficult to come up with a valid solution, and even possible to come up with all solutions by hand (though I leave this as an exercise to the reader). I also leave as an exercise to the reader how to construct a mathematically equivalent puzzle with SET cards.

Since the puzzle turns exactly like the cube, if you can solve the cube, and can find a valid configuration (easy), this puzzle is unlikely to present a challenge.

I bought this puzzle while transiting at Changi airport. Changi has a program where you can receive a 20SGD shopping voucher when transiting on Singapore Airlines. The rules of this program are constantly being tweaked and it always has an expiry date, but the promotion has continually existed in some form for at least the past five years.

Singularities of Schubert varieties within a right cell

Martina Lanini and I recently posted our preprint Singularities of Schubert varieties within a right cell to the arXiv. In it, we show that every singularity which appears in a type A Schubert variety appears between two permutations lying in the same right cell. This shows that any behaviour controlled by the singularities of Schubert varieties manifests itself within a Specht module. Some exmples are discussed.

The work was conducted during our recent visit to the thematic trimester program on representation theory at the Institut Henri Poincaré in Paris. I spent an enjoyable first month there before returning to Australia. Originally I was scheduled to be on a plane right now to return to Paris for the end of the program, but alas this is no longer possible. Oh well.

Hierve El Agua and Mitla (day trip from Oaxaca)

I was recently at Banff in Mexico (a.k.a. Oaxaca) and had the opportunity to enjoy the following day trip. All information current as of December 2019.

What: Hierve El Agua is a pretty site in the mountains/hills not too far from Oaxaca (the city). There are natural springs coming out of the rocks that have been dammed at places to create artificial pools, and the water creates stalactite-like formations on the rocks. Entrance is 25 pesos.

Mitla is a town on the way to Hierve el Agua. Located in the town is a Zapotec archaeological site, second only to (but much smaller than) Monte Alban. Entrance is 75 pesos.

How: While you can do this as an organised tour or even extravagantly hire a taxi for the day, I will describe the bus route.

From Oaxaca, take the 2nd class bus to Mitla. These are reasonably frequent, are green and have the word Mitla on the front so are easy to spot. It can be caught anywhere along the route by hailing down the bus (there are stops, but it seems you can get on the bus wherever you want). I don’t know the full route of the bus, but it turns right onto highway 190 at the Parque de Beisbol by doing a right-left-right manouver around the stadium anticlockwise. Cost 20 pesos.

Waiting at Mitla’s 2nd class bus station are the collectivos to Hierve El Agua. They are impossible to miss. They wait until they are full, and then leave, so your travel time may vary. Officially the cost was 50 pesos. I paid 60 pesos on the way there (the extra 10 pesos was to take the toll road) and 72 pesos on the way back, which was the amount needed per person to leave early with only 7 passengers. I never had to wait long to leave but others in my returning vehicle were waiting for an hour, which helped encourage them to cough up extra money to leave early.

To Do: At Hierve El Agua there is a short hike (maybe ~1 hr?). It is a loop where you go down to the valley which gives you a better look at some of the rock formations. This hike is much easier done in an anticlockwise direction as the trail is easier to find that way. The best bits are all at the start of the hike when done that way. There are also free change rooms for changing to swim in the artificial pools.

Pictures: None. Let this be a warning to me to back up pictures from my phone in a timely manner.

Puzzled Pint

I wonder perhaps if Puzzled Pint is not as well-known as it should be.

It is a monthly event, run in pubs around the world where you and your team solve a set of puzzles while, naturally, drinking a pint.

In terms of difficulty, I’d say it’s on the easier end of the puzzling spectrum, much easier than the MIT mystery hunt or other puzzle hunts I’ve seen, instead more akin to the difficulty of a typical escape room, or perhaps a bit easier. But there’s no need to take my word for it, the archive of past puzzles is available online for you to peruse.

I am fortunate that two lovely ladies have taken it upon themselves to host an edition in Melbourne over the past year.

Happy puzzling,

endpress
signoff

We’re hiring

The University of Melbourne maths department is hiring. All our ads can be found on mathjobs.

In pure maths, we have a continuing position in analysis. Applications should be submitted by the earlier deadline of 25 October to ensure full consideration.

There are also other positions available in applied and statistics, as well as a temporary position open to all areas.

Sydney Mathematical Research Institute International Visitor Program

There is a new (established in the last couple of years) mathematical institute based at the University of Sydney. I want to call attention to a visitor program they run, for mathematical visits to Australia.

They fund research visits of at least one month’s duration. At least two weeks must be spent at the University of Sydney, but the rest can be taken anywhere in Australia.

Funding rounds for these research visits happen periodically. Currently there is one open for visits within the period April-December 2020, with applications closing on 28 July.

Anyone interested should check out the research intstitute’s webpage.