Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient

Mulmuley, Ketan D. ; Narayanan, Hariharan ; Sohoni, Milind

Journal of Algebraic Combinatorics, Tome 36 (2012) no. 1, pp. 103-110.

Résumé

Summary: We point out that the positivity of a Littlewood-Richardson coefficient _boxclose_boxclose_, c^gamma_alpha, beta for $sl _{ n }$ can be decided in strongly polynomial time. This means that the number of arithmetic operations is polynomial in $n$ and independent of the bit lengths of the specifications of the partitions $\alpha , \beta $, and $\gamma $, and each operation involves numbers whose bitlength is polynomial in $n$ and the bit lengths $\alpha , \beta $, and $\gamma $. Secondly, we observe that nonvanishing of a generalized Littlewood-Richardson coefficient of any type can be decided in strongly polynomial time assuming an analogue of the saturation conjecture for these types, and that for weights $\alpha , \beta , \gamma $, the positivity of $c ^{ 2 g} _{2 a, 2 b}$ c^ 2gamma_2alpha, 2beta can (unconditionally) be decided in strongly polynomial time.

Détail

Keywords: keywords Littlewood-richardon coefficients, geometric complexity theory, algorithms