Math.Combinat.Tableaux.GelfandTsetlin

Gelfand-Tsetlin patterns and Kostka numbers.

Gelfand-Tsetlin patterns (or tableaux) are triangular arrays like

[ 3 ]
[ 3 , 2 ]
[ 3 , 1 , 0 ]
[ 2 , 0 , 0 , 0 ]

with both rows and columns non-increasing non-negative integers. Note: these are in bijection with the semi-standard Young tableaux.

If we add the further restriction that the top diagonal reads lambda, and the diagonal sums are partial sums of mu, where lambda and mu are two partitions (in this case lambda=[3,2] and mu=[2,1,1,1]), then the number of the resulting patterns or tableaux is the Kostka number K(lambda,mu). Actually mu doesn't even need to the be non-increasing.

Kostka numbers

kostkaNumber :: Partition -> Partition -> Int

Kostka numbers (via counting Gelfand-Tsetlin patterns). See for example http://en.wikipedia.org/wiki/Kostka_number

K(lambda,mu)==0 unless lambda dominates mu:

[ mu | mu <- partitions (weight lam) , kostkaNumber lam mu > 0 ] == dominatedPartitions lam

kostkaNumberReferenceNaive :: Partition -> Partition -> Int

Very naive (and slow) implementation of Kostka numbers, for reference.

kostkaNumbersWithGivenLambda :: forall coeff. Num coeff => Partition -> Map Partition coeff

Lists all (positive) Kostka numbers K(lambda,mu) with the given lambda:

kostkaNumbersWithGivenLambda lambda == Map.fromList [ (mu , kostkaNumber lambda mu) | mu <- dominatedPartitions lambda ]

It's much faster than computing the individual Kostka numbers, but not as fast as it could be.

kostkaNumbersWithGivenMu :: Partition -> Map Partition Int

Lists all (positive) Kostka numbers K(lambda,mu) with the given mu:

kostkaNumbersWithGivenMu mu == Map.fromList [ (lambda , kostkaNumber lambda mu) | lambda <- dominatingPartitions mu ]

This function uses the iterated Pieri rule, and is relatively fast.

Gelfand-Tsetlin patterns

type GT = [[Int]]

A Gelfand-Tstetlin tableau

asciiGT :: GT -> ASCII

kostkaGelfandTsetlinPatterns :: Partition -> Partition -> [GT]

kostkaGelfandTsetlinPatterns' :: Partition -> [Int] -> [GT]

Generates all Kostka-Gelfand-Tsetlin tableau, that is, triangular arrays like

[ 3 ]
[ 3 , 2 ]
[ 3 , 1 , 0 ]
[ 2 , 0 , 0 , 0 ]

with both rows and column non-increasing such that the top diagonal read lambda (in this case lambda=[3,2]) and the diagonal sums are partial sums of mu (in this case mu=[2,1,1,1])

The number of such GT tableaux is the Kostka number K(lambda,mu).

countKostkaGelfandTsetlinPatterns :: Partition -> Partition -> Int

This returns the corresponding Kostka number:

countKostkaGelfandTsetlinPatterns lambda mu == length (kostkaGelfandTsetlinPatterns lambda mu)

The iterated Pieri rule

iteratedPieriRule :: Num coeff => [Int] -> Map Partition coeff

Computes the Schur expansion of h[n1]*h[n2]*h[n3]*...*h[nk] via iterating the Pieri rule. Note: the coefficients are actually the Kostka numbers; the following is true:

Map.toList (iteratedPieriRule (fromPartition mu))  ==  [ (lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]

This should be faster than individually computing all these Kostka numbers.

iteratedPieriRule' :: Num coeff => Partition -> [Int] -> Map Partition coeff

Iterating the Pieri rule, we can compute the Schur expansion of h[lambda]*h[n1]*h[n2]*h[n3]*...*h[nk]

iteratedPieriRule'' :: Num coeff => (Partition, coeff) -> [Int] -> Map Partition coeff

iteratedDualPieriRule :: Num coeff => [Int] -> Map Partition coeff

Computes the Schur expansion of e[n1]*e[n2]*e[n3]*...*e[nk] via iterating the Pieri rule. Note: the coefficients are actually the Kostka numbers; the following is true:

Map.toList (iteratedDualPieriRule (fromPartition mu))  ==  
  [ (dualPartition lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]

This should be faster than individually computing all these Kostka numbers. It is a tiny bit slower than iteratedPieriRule.

iteratedDualPieriRule' :: Num coeff => Partition -> [Int] -> Map Partition coeff

Iterating the Pieri rule, we can compute the Schur expansion of e[lambda]*e[n1]*e[n2]*e[n3]*...*e[nk]

iteratedDualPieriRule'' :: Num coeff => (Partition, coeff) -> [Int] -> Map Partition coeff