Computing Clebsch–Gordan coefficients with Hive Polytopes and BZ-polytopes

The Maple notebooks below generate the defining inequalities for Hive polytopes ([3]) or Berenstein–Zelevinsky (BZ) polytopes ([2]) in a file-format suitable for input into LattE macchiato. LattE macchiato is a program that enumerates the integer lattice points in a rational polytope via the algorithm of Barvinok ([1]). Applying Barvinok's algorithm to the hive and BZ-polytopes yields an algorithm for computing Clebsch–Gordan coefficients that runs in polynomial time for fixed rank. In particular, enumerating the lattice points in hive polytopes yields the Littlewood–Richardson coefficients (which are the Clebsch–Gordan coefficients in type Ar).

The strength of the polyhedral algorithm is that it works for weights with very large entry sizes (at least into the millions) with little effect on the running time. On the other hand, the algorithm requires lower ranks than the standard methods, such as those based on Klimyk's formula. In this sense, polyhedral algorithm complements the standard methods. Generally speaking, the polyhedral algorithm is an effective means for computing Littlewood–Richardson coefficients for ranks r ≤ 6. For the other classical roots systems, the algorithm is effective in ranks r ≤ 4, roughly speaking. See [4] for a study of the practical effectiveness of this algorithm.

Instructions for using the Maple notebooks are in the introductory comments of each file. These files have been tested on Maple 9. They may not run on earlier versions of Maple.

Hive Polytopes (Type Ar)
BZ-polytopes for Type Br
BZ-polytopes for Type Cr
BZ-polytopes for Type Dr

References

[1]   Alexander I. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), no. 4, 769–779.

[2]   Arkady Berenstein and Andrei Zelevinsky, Tensor product multiplicities, canonical bases and totally positive varieties, Invent. Math. 143 (2001), no. 1, 77–128, arXiv:math.RT/9912012.

[3]   Anders Skovsted Buch, The saturation conjecture (after A. Knutson and T. Tao), Enseign. Math. (2) 46 (2000), no. 1-2, 43–60, arXiv:math.CO/9810180, With an appendix by William Fulton.

[4]   Jesús A. De Loera and Tyrrell B. McAllister, On the computation of Clebsch-Gordan coefficients and the dilation effect, Experiment. Math. 15, (2006), no. 1, 7–20, arXiv:math.CO/0505094.