Transcript The Computation of Kostka Numbers and Littlewood

The Computation of Kostka
Numbers and Littlewood-Richardson
coefficients is #P-complete
Hariharan Narayanan
University of Chicago
Young tableaux
1
1
1
2
2
2
3
4
3
A Young tableau of shape λ = (4, 3, 2) and
content μ = (3, 3, 2, 1).
The numbers in each row are non-decreasing from the left to
the right.
The numbers in each column are strictly increasing from the top
to the bottom.
Skew tableaux
A skew tableau of shape (2)*(2,1) and
content μ = (1, 1, 2, 1).
1
2
3
4
3
As with tableaux, the numbers in each row of a
skew tableau are non-decreasing from the left to
the right,
and the numbers in each column are strictly
increasing from the top to the bottom.
LR (skew) tableaux
A (skew) tableau is said to be LR if, when its
entries are read right to left, top to bottom, at any
moment, the number of copies of i encountered
is not less than the number of copies of i+1
encountered, for each i.
1
1
1
3
2
2
3
An LR skew tableau of shape
(2)*(2,1) and content (2, 2, 1).
1
2
2
A skew tableau of shape (2)*(2,1) and
content (2, 2, 1) that is not LR.
Kostka numbers
The Kostka number Kλμ is the number of Young tableaux having
shape λ and content μ.
If λ = (4, 3, 2) and μ = (3, 3, 2, 1),
Kλμ =4 and the tableaux are -
1
1
1
2
2
4
3
3
2
1
1
1
2
2
2
3
4
3
1
1
1
2
2
3
3
4
1
1
1
2
2
2
3
3
2
4
Littlewood-Richardson
Coefficients
Let α and λ be partitions and ν be a vector with non-negative integer
components.
The Littlewood-Richardson coefficient cλα ν is the number of LR skew
tableaux of shape λ*α that have content ν.
If λ = (2, 1), α = (2, 1) and ν = (3, 2, 1), cλα ν=2 and the LR skew
tableaux are 1
1
1
2
2
1
2
3
1
3
2
1
Representation theory
Consider the group SLn(C) of n×n matrices over complex
numbers that have determinant 1. Any matrix G = (gij) in
SL(n, C) can be defined to act upon the formal variable xi by
xi
Σ gij xj.
This leads to an action on the vectorspace T of
all polynomials f in the variables {xi} according to
G(f) x = f G-1x.
Representation theory
One can decompose T into the direct sum of vectorspaces
Vλ, where λ = (λ1 , …, λk) ranges over all partitions (of all
natural numbers n)
such that each Vλ is invariant under the action of SLn(C) and
cannot be decomposed further into the non-trivial sum of
SLn(C) invariant subspaces.
Representation theory
Let H be the subgroup of SLn(C) consisting of all diagonal
matrices.
Though Vλ cannot be split into the direct sum of
SLn(C) - invariant subspaces, it can be split into the direct sum
of one dimensional H-invariant subspaces Vλμ
Vλ = + Vλμ +K λμ ,
μ
where μ ranges over all partitions of the same number n that
λ is a partition of, and the multiplicity with which Vλμ occurs
in Vλ is K λμ , the Kostka number defined earlier.
Representation theory
The Littlewood-Richardson coefficient appears as the
multiplicity of Vν in the decomposition of the tensor product
Vλ◙Vα :Vλ◙Vα = + Vν +cλα ν
The Kostka numbers and the Littlewood Richardson
coefficients also play an essential role in the representation
theory of the symmetric groups [F97].
Related work
 Probabilistic polynomial time algorithms exist, that calculate the
set of all non-zero Kostka numbers, and Littlewood-Richardson
coefficients, for certain fixed parameters, in time, polynomial in
the total size of the input and output [BF97].
 Vector partition functions have been used to calculate
Kostka numbers and Littlewood-Richardson coefficients [C03], and
to study their properties [BGR04].
 In his thesis, E. Rassart
described some polynomiality properties
of Kostka numbers and Littlewood-Richardson coefficients, and
asked if they could be computed in polynomial time [R04].
The problems are in #P
Kostka numbers :
 A tableau is fully described by the number of
copies of j that are present in its ith row. This description has
polynomial length.
 Given such a description, one can verify whether it corresponds
to a tableau of the required kind, in polynomial time, by
checking
 whether the columns have strictly increasing entries, from the
top to the bottom, and that
 the shape and content are correct.
The problems are in #P
Littlewood Richardson coefficients :
 An LR skew tableau λ*α is fully described by its shape and the
number of copies of j that are present in the ith row of it.
 This description has polynomial length.
 Given such a description, one can verify whether it corresponds
to an LR skew tableau of the required kind by checking
 whether the columns have strictly increasing entries, from the
top to the bottom,
 that the shape and content are correct and
 that the skew tableau is LR.
 Each can be verified in polynomial time.
Hardness Results

We prove that the computation of the Kostka number Kλμ is #P
hard, by reducing to it, the #P complete problem [DKM79] of
computing the number of 2 × k contingency tables with given
row and column sums.

The problem of computating the Littlewood – Richardson
coefficient cλα ν is shown to be #P-hard by reducing to it, the
computation of the Kostka number Kλμ.
Contingency tables

A contingency table is a matrix of non-negative integers
having prescribed row and column sums.
4
3
3
2
2
Contingency tables
Counting the number of 2 × k contingency tables with given row
and column sums is #P complete. [DKM79]
Example:
A contingency table with row sums a = (4, 3) and column sums b =
(3, 2, 2) :-
2
1
1
4
1
1
1
3
3
2
2
Reduction to computing Kostka
numbers
We shall exhibit a reduction from the problem
of counting the number of 2 × k contingency
tables with row sums a = (a1, a2), a1 ≥ a2
and column sums b = (b1, …, bk)
to the set of Young tableau having shape

λ = (a1+a2, a2) and content μ = (b, a2).
RSK correspondence

The Robinson Schensted Knuth (RSK) correspondence gives a
bijection between the set I(a, b) of contingency tables having
row sums a, column sums b,
and the set U T(λ’, a) × T(λ’, b) of pairs of tableaux having
contents a and b respectively.
C
RSK correspondence
2
1
1
1
1
1
P
Q
RSK correspondence
1
1
1
1
1
1
P
1
Q
1
RSK correspondence
0
1
1
1
1
1
P
1
Q
1
1
1
RSK correspondence
0
0
1
1
1
1
P
1
Q
1
2
1
1
1
RSK correspondence
0
0
0
1
1
1
P
1
Q
1
2
3
1
1
1
1
RSK correspondence
0
0
0
0
1
1
P
Q
1
1
1
2
3
1
1
1
1
RSK correspondence
0
0
0
0
1
1
P
1
2
Q
1
1
3
1
2
1
1
1
RSK correspondence
0
0
0
0
0
1
P
Q
2
1
2
1
1
3
1
2
1
1
1
RSK correspondence
0
0
0
0
0
1
P
Q
1
1
2
3
1
2
1
1
2
2
1
1
RSK correspondence
0
0
0
0
0
0
Content P = (3, 2, 2) = b
Content Q = (4, 3) = a
P
Q
1
1
2
3
1
2
3
1
1
2
2
1
1
2
RSK correspondence

Thus, the RSK correspondence gives us the
identity |I(a, b)| = Σ Kλ’aKλ’b
 Kλ’a > 0 implies that λ1 ≥ a1 and that λ2 ≤a2
,
but b is arbitrary, so the summation is over a set
exponential in the size of (a, b).
RSK correspondence
Q is fully determined by its
shape and content since it has
only 1’s and 2’s.
Content P = b
Content Q = a
In other words Kλ’a > 0
implies that Kλ’a = 1.
P
1
1
2
3
1
Q
2
3
1
1
2
2
1
1
2
RSK correspondence
The shape of P and Q
could be any s = (s_1, s_2)
such that s_1 ≥ a_1 and s_2 ≤a_2,
but none other.
Content P = b
Content Q = a
P
1
1
2
3
1
Q
2
3
1
1
2
2
1
1
2
Reduction to computing Kostka numbers
Extend P
by padding it with
copies of k+1 to a tableau T of
shape λ and content μ, where λ =
(a_1 + a_2, a_2) and μ = (b, a_2).
1
1
1
2
3
4
2
3
4
4
In our example, shape
λ = (7, 3), and
content μ = (3, 2, 2, 3).
From Contingency tables to Kostka numbers
2
1
1
1
1
1
1
1
2
3
4
1
2
3
4
4
Row sums a = content of Q= (4, 3),
Column sums b = content of P = (3, 2, 2),
shape λ = (7, 3), and content μ = (3, 2, 2, 3).
1
1
2
3
1
1
2
2
1
2
3
P
1
1
2
Q
From Kostka numbers to LittlewoodRichardson coefficients
Given a shape λ, content μ = (μ1,…, μs ),
let α = (μ2, μ2+μ3 , …, μ2+…+μs), and let ν = λ + α
Claim: Kλμ = cλα ν
From Kostka numbers to LittlewoodRichardson coefficients
T
S
1
1
1
2
3
4
2
1
1
1
2
3
4
3
2
4
3
4
4
4
1
1
1
1
1
2
2
2
2
2
3
3
3
1
1
From Kostka numbers to LittlewoodRichardson coefficients
Any tableau of shape λ and content μ, can be
embedded in an LR skew tableau of shape
λ*α, and content ν.

1
1
1
2
3
4
2
3
4
4
From Kostka numbers to LittlewoodRichardson coefficients
Any tableau of shape λ and content μ, can be
embedded in an LR skew tableau of shape
λ*α, and content ν.

1
1
1
2
3
4
2
3
4
4
1
1
1
1
1
2
2
2
2
2
3
3
3
1
1
From Kostka numbers to LittlewoodRichardson coefficients
Any LR skew tableau of shape λ*α and
content ν, when restricted to λ, has content μ.

1
1
1
2
3
4
2
3
4
4
1
1
1
1
1
2
2
2
2
2
3
3
3
1
1
From Kostka numbers to LittlewoodRichardson coefficients
Any LR skew tableau of shape λ*α and
content ν, when restricted to λ, has content μ.

1
1
1
2
3
4
2
3
4
4
Future directions

Do there exist Fully Polynomial Randomized
Approximation Schemes (FPRAS) for the
evaluation of these quantities?
Thank You!
References






[BF97] A. Barvinok and S.V. Fomin, Sparse interpolation of
symmetric polynomials, Advances in Applied Mathematics, 18
(1997), 271-285, MR 98i:05164.
[BGR04] S. Billey, V. Guillimin, E. Rassart, A vector partition
function for the multiplicities of slk(C), Journal of Algebra, 278 (2004)
no. 1, 251-293.
[C03] C. Cochet, Kostka numbers and Littlewood-Richardson
coefficients, preprint (2003).
[DKM79] M. Dyer, R. Kannan and J. Mount, Sampling Contingency
tables, Random Structures and Algorithms, (1979) 10 487-506.
[F97] W. Fulton, Young Tableaux, London Mathematical Society
Student Texts 35 (1997).
[R04] E. Rassart, Geometric approaches to computing Kostka
numbers and Littlewood-Richardson coefficients, preprint
(2003).