Although I generally like reading mathematical concepts on Hacker News, this seems a little steep...
> The traditional application of Young's lattice is to the description of the irreducible representations of symmetric groups Sn for all n, together with their branching properties, in characteristic zero.
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!).
I am not sure I understand your question. What is true is that: starting from the root of the Young lattice, a forward path of n steps corresponds to a non-increasing partition of n. For instance, in the wiki picture of the lattice, the path up-left-left-right from the root corresponds to the partition 4=3+1.
Now, if you are asking whether these paths/partitions are related to actual paths in the vector spaces that are representations of the symmetric groups, no; the connection between these Young diagrams to representations is much more indirect.
First i'm not trained in these fields but I felt that partitions were combinations of elements (vectors in that space, the path being the additive operation) and a partition would just be the set of all paths. I don't know if that makes much sense.
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]
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.
absolutely agree, probably the worst general category in wikipedia, feels very much Bourbakian, extreme rigor and nothing else. Worst way to teach/introduce math imho.
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.
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.
16 comments
[ 5.5 ms ] story [ 8.6 ms ] thread> The traditional application of Young's lattice is to the description of the irreducible representations of symmetric groups Sn for all n, together with their branching properties, in characteristic zero.
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!).
Now, if you are asking whether these paths/partitions are related to actual paths in the vector spaces that are representations of the symmetric groups, no; the connection between these Young diagrams to representations is much more indirect.
The wikipedia section https://en.wikipedia.org/wiki/Young_tableau#Applications_in_... has a decent (maybe) exposition of the connection, but to get the full picture of the connection, you need a dedicated study of this topic.
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
It's great as a reference, though.
And reading old books, or even encyclopedia, there was a clear human element.. a semi cohesive narrative that made discovery a lot better.
Maybe for people who already know enough, wikipedia can be a good source of extension.
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.
I found the poset aspect of partitionning pretty. Also the page links to https://en.wikipedia.org/wiki/Young%E2%80%93Fibonacci_lattic... because apparently the structure embodies a fib sequence. Quite cool