Young's Lattice

HN has a mechanism to "boost" older submissions that didn't get attention but are judged interesting by the mods by putting them back in with a fudged newer timestamp.

It is steep, but at the same time, representation theory is so damn beautiful; for anyone with the time and interest to pursue a pure mathematical topic as a hobby, I highly recommend combinatorial representation theory. Besides, representation theory seems to be of great importance to computer science. The first explicit examples of expander graph families, for instance, were given by Grigori Margulis using deep theorems from unitary representation theory (see A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures for instance).

Regarding the sentence you posted, it is a bit less scary than it sounds. Let's break down the concepts.

Symmetric group of order N: it is the collection of all rearrangements of N distinct symbols on a line. This collection satisfies the axioms of a permutation group, which very roughly means a self-contained collection of permutations.

Representations of... (a group): Abstract groups are opaque objects in general, but some particular groups tend to express information vividly in their elements and structure. The most computationally rich example is groups of linear transformations on a vector space: rotations, reflections, shears etc. A linear representation of an abstract group is a realization of the group as a group of linear transformations: you pick a vector space, and let each group element correspond to some linear transformation on the vector space, so that the product of group elements corresponds to the composition of linear transformations. Now you can use the power of linear algebra to study your abstract group.

Irreducible representations of... (a group): Now that you have realized your group as a group of transformations on a vector space, maybe you get the following behavior: the group takes a subspace of that vector space and transforms it into itself. And takes the complementary part of that vector space, and transforms that into itself. Well, then you can study the two subspaces separately because they are never "mixed" by the group. That is called a reduction, and such a representation is called reducible. If you cannot do that, you have an irreducible representation. These act like the prime numbers of representation theory, at least where finite groups are concerned: every representation splits as a sum of irreducibles, and the deepest linear information about the group is carried in them.

Branching properties: so now you have an irreducible representation of a symmetric group. Every group of permutations of N elements is a subgroup of that group, so what happens if you focus your attention to the subgroup, and forget about all the transformations that are not in the subgroup? The resulting representation may not be irreducible anymore: some transformations that mixed vector spaces may not be in the smaller group. If it is not irreducible, how does it split into irreducible representations? In particular, how many irreducible components are there and how many times does each component appears? The answer to those questions are the branching rules for the restricted representation to the subgroup. In general, it is an extremely difficult problem, but it has been resolved for some families of groups, the symmetric groups being a primary example (where the rules are given in terms of, well, Young tableaux and the linked Young lattice!).

Let me try (and probably fail) to translate some of that.

S_n is the collection of permutations on n symbols with a multiplicative structure. In python

from itertools import permutations

n = 6

S_n = list(permutations(range(n)))

multiply = lambda alpha, beta: [alpha[x] for x in beta]

This is the reason why Substitution-Permutation networks interleave permutations with non-permutations. Two permutations in a row is just a permutation. "Representation Theory" is the art of taking such multiplicative structures and associating every object with a matrix so that the matrix multiplication encodes the original objects multiplication. This is useful because mathematicians know so much about matrices.

For example if you define

matrix = lambda perm: [[1 if i == j else 0 for j in range(n)] for i in perm]

matrix(alpha) * matrix(beta) == matrix(multiply(alpha, beta))

However, it is desirable to represent it as matrices in a more "efficient manner". For example S_3 can be written using only two dimensions. Representation theory deals with stuff like minimal representation.

If you snake from the bottom of young's lattice upwards to a specific diagram you can record the information into a young tableau by writing in the cell when it was added. Young tableau are very mathematically rich, but here is an "application" of them.

If you have a balanced parenthesis (the dyck langauge), [[[][]][]] and you record two list of when you open and when you close

[0, 1, 2, 4, 7]

[3, 5, 6, 8, 9]

you get a two-by-n young tableau, since the grid is increasing horizontally and vertically.

Other special shapes of young tableau can encode other interesting structures. Also see TAOCP V3 5.1.4, or google the RSK correspondence.

edit 1: newlines edit 2: fixed python

Wikipedia's explanations of mathematical concepts just aren't very good unfortunately.

A subset of this can be explained relatively simply:

A permutation on n elements is a way to reorder lists of length n. One way to represent it is how it reorders 1, 2, …, n, but this doesn’t show you much structure.

It turns out that one can group a permutation into independent cycles. One reason this is useful is because you might want to ask about applying the same permutation repeatedly and cycles are a way to do that.

A cycle is the part of a permutation that can be described as a (circular) list where each element is transformed into the one following it. For example we might write the cycle (1257) to indicate the permutation that takes 1 to 2, 2 to 5, 5 to 7, and 7 to 1. It turns out that any permutation of a finite set can be written as a product of disjoint cycles (apart from the choice of which order to write down the cycles and the first element of each cycle).

Another question is what happens if you “change your view” when applying a permutation. That is, instead of applying p to reorder some list, first apply a permutation q, then p, then undo q. For example instead of modifying p to make it work on a list backwards you could reverse the list, then apply p, then unreverse it.

It turns out that this operation cannot change the ‘shape’ of p. That is, it can change the numbers in the cycle but if p was a 3-cycle, two 5-cycles, and a 1-cycle (an n-cycle is a cycle with n elements) then the combination [q, p, undo_q] will also be a 3-cycle, two 5-cycles, and a 1-cycle. Furthermore, there always exists a a to transform between any two cycles with the same shape.

Now notice that the elements of Young’s lattice – partitions of integers (ways to find a multi set of numbers that add up to a given total) – correspond to the different possible shapes of permutations.