The honeycomb model for tensor product multiplicities

Allen Knutson Mathematics Department

Brandeis University

Terence Tao Mathematics Department

UCLA Chris Woodward

Mathematics Department

Rutgers University

www.math.ucla.edu/∼tao/preprints

Abstract

Let V_{λ}, V_{μ}, V_{ν} be three irreducible representations of U(n). The Littlewood-Richardson co-efficient c_{λμ}^{ν} is defined as the multiplicity in which V_{ν} appears in the tensor product V_{λ} ⊗ V_{μ}. These co-efficients are fundamental to the representation theory of U(n), but many very basic questions about them have only been settled recently. We discuss recent progress in the study of these co-efficients using a new model known as the honeycomb model.

Representations of U(n)

• The finite-dimensional irreducible representations of U(n) can be written (up to isomorphism) as V_{λ}, where λ = (λ_{1}, …, λ_{n}) is the highest weight of V_{λ}, and be any non-increasing sequence of integers. The characters χ_{λ} associated to each representation form an orthogonal basis of L^{2}(U(n))_{U(n)}, thanks to the Peter-Weyl theorem.

• The representations V_{λ} can be constructed abstractly via the Borel-Weil theorem, and more explicitly using symmetric functions and Young tableaux, but these characterizations are difficult to work with directly. The fundamental weights (1, …, 1, 0, …, 0) correspond to exterior algebra representations ⋀^{k} C^{n}, where k is the number of 1’s. All the other representations can be reconstructed in principle from tensor products of these fundamental representations (together with the rather trivial inverse determinant representation (−1, …, −1)).

• The tensor product V_{λ} ⊗ V_{μ} of two irreducible representations is not irreducible in general, but it does of course split into irreducible components:

V_{λ} ⊗ V_{μ} = ⨁_{ν} V_{ν}^{c_{λμ}^{ν}}

The co-efficients c_{λμ}^{ν} are non-negative integers and are known as Littlewood-Richardson coefficients. The study of these co-efficients is a basic problem in the representation theory of U(n), and also has application to the theory of co-adjoint orbits in U(n) (in particular, the sum of Hermitian matrices problem), the Schubert calculus of flag varieties, sub-modules of p-groups, and several other areas. A question of particular importance is determining when c_{λμ}^{ν} ≠ 0; i.e. determining what irreducible representations appear at all in V_{λ} ⊗ V_{μ}.

• On the character level, the Littlewood-Richardson co-efficients give a characterize pointwise multiplication in the character basis:

χ_{λ}χ_{μ} = ∑_{ν} c_{λμ}^{ν}χ_{ν}.

• There are several ways to compute Littlewood-Richardson co-efficients. One way is to first consider the easy case when V_{λ} or V_{ν} is a fundamental representation; this is given by Pieri’s rule (which we’ll give later).

The general case can then be deduced (in principle, at least) from a large number of applications of the associativity law

∑_{ν} c_{λμ}^{ν}c_{νγ}^{δ} = ∑_{ν} c_{λν}^{δ}c_{μγ}^{ν}

which reflects the associativity of tensor products (or pointwise multiplication). This approach, although useful theoretically, is abysmal for computational purposes.

• Another way goes through the Weyl character formula (which explicitly describes the Fourier transform of characters on a maximal torus), and gives the formula

c_{λμ}^{ν} = C ∫_{T^{n}} \frac{∑_{α,β∈S_{n}} sgn(αβ)e^{2πi([ν−α(λ)−β(μ)+ρ]·ξ} dξ}{∏_{1≤j≤k≤n}(e^{2πi(ξ_{k}−ξ_{j})} − 1)}

where S_{n} is the symmetric group, T^{n} = R^{n}/Z^{n} is the maximal torus of U(n), and ρ is half the sum of the positive weights of U(n). Although this is quite explicit and useful for some purposes, it is not good in determining whether c_{λμ}^{ν} ≠ 0. Indeed, it is not even clear from the formula that c_{λμ}^{ν} is always a non-negative real [the easiest way is via associativity and verifying non-negativity for the exterior algebra representations].

• A third way is via Young tableaux. Every (positive) weight λ can be associated to a Young tableau T_{λ} (a certain pattern of unit squares in the plane). The coefficient c_{λμ}^{ν} can be computed as the number of ways that a compound tableau T_{λ} +T_{μ} can be re-arranged into the tableau T_{ν} using the rules of a certain “sliding game” (jeu de taquin). This rule is known as the Littlewood-Richardson rule; it is traditionally proven by first verifying Pieri’s rule (fairly easy), and showing that the sliding game is associative (not easy at all!)

• This talk will be centered around a fourth way to compute Littlewood-Richardson co-efficients based on the honeycomb model.

A simpler problem: Weight multiplicities

• To motivate the honeycomb model, we first consider the simpler problem of weight multiplicities of U(n) irreducible representations V_{λ} = V_{λ^{(n)}} under the action of the maximal torus T^{n}.

• Since U(n) acts on V_{λ}, the torus T^{n} does also. As a T^{n} representation, V_{λ} is not irreducible, and splits up into one-dimensional representations R_{ν} (indexed by Z^{n}), with each representation R_{ν} appearing c_{λ}^{ν} times. On the character level, the weight multiplicities c_{λ}^{ν} are abelian Fourier coefficients of the character χ_{λ}:

χ_{λ}(ξ) = ∑_{ν} c_{λ}^{ν}e^{2πiν·ξ} ∀ξ ∈ T^{n}.

• The weight multiplicities are closely related to the Littlewood-Richardson numbers. For instance, the Weyl character formula gives a very similar description of these co-efficients:

c_{λ}^{ν} = C ∫_{T^{n}} \frac{∑_{α∈S_{n}} sgn(α)e^{2πi([ν−α(λ)+ρ]·ξ} dξ}{∏_{1≤j≤k≤n}(e^{2πi(ξ_{k}−ξ_{j})} − 1)}

• Another way to analyze the T^{n} action on U(n) representations is to introduce the sequence of Cartan subgroups

T^{n} = U(1)×T^{n−1} ⊂ U(2)×T^{n−2} ⊂ … ⊂ U(n−1)×T^{1} ⊂ U(n);

this requires one to choose an ordered basis of T^{n}, thus breaking Weyl symmetry. The group U(k) × T^{n−k} are those unitary matrices which consist of an upper left k × k unitary block, and n − k additional diagonal unitary entries, with all other entries being zero.

• We now proceed inductively, first breaking up a U(n) representation V_{λ^{(n)}} into irreducible U(n − 1) × T^{1} components. This splits V_{λ^{(n)}} into components V_{λ^{(n−1)}}⊗ R_{ν_{n}}, where λ^{(n−1)} is a U(n − 1) highest weight (i.e. an n − 1-tuple of non-increasing integers), and the integer ν_{n} is determined by the trace identity

λ_{1}^{(n)} + … + λ_{n}^{(n)} = λ_{1}^{(n−1)} + … + λ_{n−1}^{(n−1)} + ν_{n}.

coming from considering the circle action of the center of U(n).

• Gelfand and Cetlin observed that the U(n−1) weights must intersperse the U(n) weights:

λ_{i}^{(n)} ≥ λ_{i}^{(n−1)} ≥ lambda_{i+1}^{(n)} ∀1 ≤ i ≤ n − 1.

Conversely, every U(n−1) weight which intersperses the U(n) weight appears exactly once in the above decomposition.

• Iterating this decomposition, we can obtain a complete decomposition of V_{λ^{(n)}} into one-dimensional T^{n}- invariant spaces, parameterized by a sequence λ^{(1)}, …, λ^{(n−1)} of U(1), …, U(n − 1) weights such that each λ^{(i)} intersperses λ^{(i+1)}. The T^{n} weight ν of this space is given by the trace formulae

λ_{1}^{(i)} + … + λ_{i}^{(i)} = λ_{1}^{(i−1)} + … + λ_{i−1}^{(i−1)} + ν_{i}.

Pictorially, we can index T^{n}-invariant components of V_{λ} by Gelfand-Cetlin pyramids:

10

The honeycomb model

• We now describe the honeycomb model for Littlewood-Richardson co-efficients. It is convenient to shift to a symmetric formulation. Let c_{λμν} denote the dimension of the U(n) invariant subspace of V_{λ} ⊗ V_{μ} ⊗ V_{ν}, or equivalently

c_{λμν} = C ∫_{U(n)} χ_{λ}χ_{μ}χ_{ν}.

These numbers are related to the standard Littlewood-Richardson numbers by the duality relationship c_{λμ}^{ν} = c_{λμν̃}. From the circle action of the center of U(n) we see that the trace condition

λ_{1} + … + λ_{n} + μ_{1} + … + μ_{n} + ν_{1} + … + ν_{n} = 0

is necessary for c_{λμnu} = 0.

• It is thus natural to place honeycombs on the plane

{(x, y, z) ∈ R^{3} : x + y + z = 0}.

This plane as three natural families of lines, x = const, y = const, z = const, at 120 degree angles to each other. We call const the constant co-ordinate of these lines, and say that the line is integral if the constant co-ordinate is an integer.

• An integral honeycomb with boundary data λ, μ, ν is defined to be any diagram of the following shape, where all the edges are lines of one of the above three types with integer co-ordinates, and have nonnegative length:

• Theorem (Knutson, T. ’98). c_{λμν} is equal to the number of integral honeycombs with boundary data λ, μ, ν.

Justification of the honeycomb model

• Allen Knutson and I conjectured the above theorem in ’95, but were only able to prove it in small dimensions and in extreme cases. The first proof came in ’98 by linking honeycombs to Berenstein-Zelevinsky patterns, which were demonstrated in ’92 to be equivalent to the Littlewood-Richardson rule using the combinatorics of Young tableaux. (Later, Bill Fulton found a more direct relationship between honeycombs and the Littlewood-Richardson rule using Young tableaux combinatorics).

• A second proof was discovered independently by Chris Woodward and Gleizer-Postnikov, both in ’99. The idea is to first verify Pieri’s rule, which states that if λ is fundamental (only consists of 0s and 1s) then c_{λμν} = 1 if μ intersperses ν and the trace condition is satisfied, and is 0 otherwise. This is easily verified in the honeycomb model:

• The next step is associativity. This basically states that the boundary value problem in the first bi-honeycomb has the same number of integer solutions as the problem in the second bi-honeycomb:

• A one-to-one correspondence can be established by scattering theory. Imagine that each vertex of the above bi-honeycombs is a particle with a given velocity. Collisions are handled by the diagram below. The scattering limit of this kinematic system gives the desired one-to-one map.

• All the known proofs of the validity of the honeycomb model are combinatorial. It would be very nice to have a representation theoretic explanation of the model (as there is for the Gelfand-Cetlin system).

The discrete polytope of weights

• Suppose we fix λ and μ, and ask what the set of all possible ν are such that c_{λμν} is; equivalently, we fix two of the sides of an integer honeycomb and ask what are the possible outcomes of the third side. In ’56 Horn conjectured that this set was given as the integer points of a certain recursively described polytope; this conjecture was verified by Knutson and myself in ’98.

• One way to study this problem is by looking at extreme values of ν, i.e. look at honeycombs which maximize some linear functional of ν. It turns out that this is only possible when the honeycomb splits as the overlay of two simpler honeycombs.

• From this and some linear algebra one can conclude that the set of all possible ν is contained in a certain polytope. To clinch Horn’s conjecture, one has to show that every integer point inside this polytope is actually attained.

• It is fairly easy to show that every point inside the polytope comes from a real honeycomb - i.e. a honeycomb in which the edge constant co-ordinates need not be integers. So the issue is to show how to convert a real honeycomb into an integer honeycomb without changing the boundary data. This is known as the saturation problem. An equivalent formulation is: If c_{NλNμNν} ≠ 0 as N → ∞, does this imply that c_{λμν} ≠ 0?

• The solution to the saturation problem comes by “inflating” the hexagons in a given real honeycomb indefinitely, until it is not possible to inflate any more hexagons or combination of hexagon. It turns out that the extremal honeycomb obtained in this way has a certain tree structure, which forces it to have integer interior of the boundary is interior (see poster).

• With a little more work, one can prove Horn’s conjecture, which also gives a complete description of the set of eigenvalues of a matrix A + B given the eigenvalues of the Hermitian matrices A and B separately.

Fulton’s conjecture

• More recently, Allen Knutson, Chris Woodward, and myself have analyzed the extreme values of ν a bit further, and have managed to characterize the set of λ, μ, ν when c_{λμν} = 1; in other words, the representation (V_{ν})^{∗} appears exactly once in V_{λ} ⊗ V_{ν}. In particular, we have shown a conjecture of Fulton that

c_{NλNμNν} = 1 ⟺ c_{λμν} = 1.

The backwards implication follows from the saturation theorem, but the forward implication is nontrivial. (It is easy to show that c_{NλNμNν} ≥ c_{λμν}, though).

• The key is to show that c_{λμν} = 1 occurs if and only if the honeycomb is rigid, in that there are no degrees of freedom if the boundary data is fixed. Generically a honeycomb is not rigid because of the presence of freely movable hexagons, but if the honeycomb has degenerated to a consistently oriented overlay then rigidity obtains:

• If a honeycomb is rigid it is trivial that the Littlewood-Richardson co-efficient is 1. However, it is not obvious that a non-rigid honeycomb cannot also have a Littlewood-Richardson co-efficient of 1. The problem is that a non-rigid honeycomb may only be able to be perturbed by a distance strictly less than 1 (e.g. 1/2), so that there is only one integer honeycomb satisfying the specified boundary conditions. To show that this doesn’t happen, we show that every non-rigid honeycomb must contain a loop which can be enlarged or shrunk by precisely 1 unit, thus showing that there are at least two integer honeycombs so that c_{λμν} > 1.