Kazhdan-Lusztig-Vogan Polynomials for E8

The atlas software written by Fokko du Cloux can compute (among other things) Kazhdan-Lusztig-Vogan polynomials for real groups. The input is a real reductive group G (specified by a real form of a complex reductive group) and a block B of representations of G with regular integral infinitesimal character. The block B is a Z-module, with two bases: one consisting of irreducible representations, and the other of standard representations. The number of basis elements is called the block size. The Kazhdan-Lusztig-Vogan polynomials (evaluated at 1) give the change of basis matrix; it is a square matrix of size the block size.

The software computes Kazhdan-Lusztig-Vogan polynomials for all groups up to rank 7 quite quickly. See the atlas tables of structure and representation theory. The complex group E8 has three real forms: the compact form, the quaternionic form (K=A1×E7) and the split form (K=D8). Each of these gives rise to a different kind of real group of type E8. Their blocks, and their sizes, are given by the blocksizes command of atlas:

compactquaternionic split

The last row means that the split group has 3 blocks (at infinitesimal character rho), of sizes 1,  73,410 and 453,060 respectively. (The columns give the group on which the Vogan-dual block lives.)

Kazhdan-Lusztig-Vogan polynomials for the compact and quaternionic groups of type E8 are easily computed, as well as those for the blocks of sizes 1 and 73,410 of the split group. That leaves the block of size 453,060 of the split group.

Computation of Kazhdan-Lusztig-Vogan Polynomials for the large block of split real E8

In principle the atlas software can compute Kazhdan-Lusztig-Vogan polynomials for the block B of size 453,060. However this would require about 200 gigabytes of virtual memory (and therefore certainly a 64-bit processor; 32-bit processors as are found in most PCs cannot possibly address more than 4 gigabytes of virtual memory); moreover this virtual memory should preferably be actual RAM, since once the program starts assigning part of its memory to disk (swap space) its speed becomes orders of magnitude slower. In fact Dan Barbasch successfully completed this calculation on a machine with 128 gigabytes of RAM and 100 gigabytes of swap space. It took 2 days to use up the RAM, and ran for another 12 days using swap space. Dan was then unable to save the answer in a usable form, since the usual textual output format of the atlas would have required more space than would be available on even very large hard disks.

David Vogan started working on this computation over the summer with Fokko (until his death from ALS in November), and in the fall also with Marc van Leeuwen. Birne Binegar did some experiments to get estimates on the size of the computation, and it became clear that even with improved efficiency it would not be possible to do this on a machine with less than 128 gigabytes of RAM.

Following a suggestion of Noam Elkies, David and Marc rewrote the code to compute the polynomials mod n for several values of n, and then obtain the answer using the Chinese remainder theorem. In the end it was necessary to compute four moduli: 251, 253, 255 and 256, which together give the answer modulo N=4,145,475,840. While it is not a-priori possible to prove this is sufficient, to fact that all coefficients modulo N were found to lie in the interval from 0 to 11,808,808 allows us to prove that these coefficients are in fact the correct ones in Z.

The computation were carried out on sage, which was kindly made available to us by William Stein. It has 64 gigabytes of RAM (and 75 gigabytes of swap, which were however not needed) and 16 AMD opteron 64-bit processors. It is physically located at the University of Washington in Seattle, but was operated for this calculation exclusively via the internet. Manual intervention in Seattle was needed several times however, to reboot the computer after crashes (which were unrelated to the atlas computation).

The calculation took place in several steps, between Friday 22 December 2006 and Monday 8 January 2007: this included four runs of the atlas software that were identical except for the modulus used, and finally several post-processing steps of the binary files written, to perform the lifting by the Chinese remainder theorem of 13,721,641,221 polynomial coefficients. The computation took about 77 hours total, if one excludes the runs that had to be aborted due to a crash or that produced useless output due to subtle bugs that were initially present in the I/O procedures. David wrote a more detailed narrative of the process of computing these polynomials.

The final answer is contained in a pair of binary files of respective sizes 14 gigabytes and 60 gigabytes. (By way of comparison, the size of the latter file would allow storing 45 days of continuous music in MP3-format.) There is a utility to print any particular Kazhdan-Lusztig-Vogan polynomial. Our next step is to make the answer available in a useful way. It is not practical to give the answer in the same form as used in the tables referred to above, for example the one for the Kazhdan-Lusztig-Vogan polynomials for the large block of Spin(5,4) (which has type B4).

The Kazhdan-Lusztig-Vogan polynomials are polynomials in an indeterminate q. The matrix alluded to above is given by evaluating at q=1. According to the table below, there is a standard representation which contains a certain irreducible representation with multiplicity 60,779,787.

Here is some information on the Kazhdan-Lusztig-Vogan polynomials for the block B.

Size of the block: 453,060

Number of distinct polynomials: 1,181,642,979

Maximal coefficient: 11,808,808

Polynomial with the maximal coefficient: 152q22 + 3,472q21 + 38,791q20 + 293,021q19 + 1,370,892q18 + 4,067,059q17 + 7,964,012q16 + 11,159,003q15 + 11,808,808q14 + 9,859,915q13 + 6,778,956q12 + 3,964,369q11 + 2,015,441q10 + 906,567q9 + 363,611q8 + 129,820q7 + 41,239q6 + 11,426q5 + 2,677q4 + 492q3 + 61q2 + 3q

Value of this polynomial at q=1: 60,779,787

Size of the matrix: 205,263,363,600=453,0602

Number of coefficients in distinct polynomials: 13,721,641,221

Tables of structure theory and representations   Atlas software   Atlas home page