Research with Undergraduates | Leonard L. Scott

Computer Investigations in Group Representation Theory

This project centered first on computational aspects of a conjecture in group representation theory, called the Lusztig conjecture (G. Lusztig, MIT, 1979). One of the ingredients of this conjecture are certain polynomials, called Kazhdan-Lusztig polynomials, which appear now to provide quite useful information about representations even when the original conjecture does not apply, and have led to new conjectures. Before further discussion, it might be best to talk about the context much more broadly, since readers of this page, especially undergraduates, might have considerably different backgrounds.

Groups are conventionally described as the abstract engines of symmetry, the latter viewed as produced through sets of tranformations of a system (possessing the symmetry) to itself. For example the symmetry inherent in a circle may be expressed by saying it remains the same figure after any rotation around its center is performed. Though harder to visualize, there are symmetries in the physical laws of nature and in the patterns of 0's and 1's in reliable electronic data transmissions. In all cases the symmetry can be viewed in terms of sets of transformations which take the system to itself. The sets of transfromations themselves are viewed as providing a representation of a given "group," which may have other representations. These other representations of the same group may produce quite different symmetry effects, but are identifiable, through the ways the transformations involved interact with themselves, as coming from the same source. The symmetries effected in a given system, more than giving some aesthetically pleasing pattern, can provide important constraints for the behavior of other objects or systems intereacting with the given system. As suggested, above groups and their representations are used in physics to describe physical laws, and these provide constraints for all behavior in nature. In communications theory group representations enter into man-made rules restricting which patterns of 0's and 1's might appear in accurate communications, as opposed to those received with an error. There are many other uses of group representation theory, both in applied areas and within mathematics itself.

In both of the applications discussed above, to physics and communications theory, the representations are "linear," effected through sets of matrices acting on systems living in some linear space of coefficients. The coefficients in the physics case are generally continuous in nature, as are the groups involved. (There are discontinuous "jumps"; which take place in the quantum world, but they are possible in quantum theory because the underlying groups can have different representations. Nevertheless, the transformations in each representation are of a continuous nature.) This continuous nature of the groups involved has helped enable a good understanding of their linear representation theory. However, much of the representation theory important for the information age involves finite coefficient systems, and the groups involved are typically finite in nature. Their representation theory is much more poorly understand, even when the groups are finite analogs of those studied in the continuous cases. The Lustig conjecture mentioned above is one of the fundamental issues in this area. It purports to give concise descriptions of the irreducible matrix representations (basic building blocks) of all the finite groups of Lie type (those that are most closely related to the continuous groups) over finite coefficient systems of modestly large size. Probably the most interesting cases for applications are the smaller coefficient systems (e.g, a single 0 and 1), but a good solution to the Lusztig conjecture could provide insight into these cases as well. Computationally, the larger coefficient systems, such as those dealt with by the Lusztig conjecture, are the most difficult.

Returning now to the project itself, we note that it has often been supported by NSF and, originally, was funded by their REU program (Research Experience for Undergraduates). It has also received funds from our UVa Mathematics Department. The first undergraduate involved was Mike Konikoff, and his place was taken by Chris McDowell, now also graduated, both in the late 90’s. Their work not only settled cases of the Lusztig conjecture (see below), but also led to the well-received byproduct [80] published in 2003 of producing (infinitely many) counterexamples to a published conjecture on finite group 1-cohomology. Continuing in this tradtion, the work of my 2012-2013 student, Tim Sprowl, has played a role in finding counterexamples to the Wall conjecture (1961) on maximal subgroups of finite groups. See the Fall 2012 newsletter of the American Institute of Mathematics at www.AIMath.org. Let me mention here that Frank Luebeck of Aachen played a central role in these Wall conjecture counterexamples, and Bob Guralnick of USC made essential observations. All of these counterexamples emerged from calculations of "Kazhdan-Lustig polynomials"; entering in the Lusztig conjecture. (When coefficients in these plynomials are input into other theoretical tools, in cases where the Lusztig conjecture is known to be true, the results can have powerful consequences in seemingly distant areas.) Computer calculations can also have positive spin-offs from unexpected phenomena observed. Such observations from Konikoff’s program are credited in the 2009 paper [87] as the original catalyst for the notion of a "semistandard filtration" introduced there. Undergraduate UVa students since the time of McDowell and Konikoff include (in addition to my current student, Kyle Stolcenberg) Jim Apple, Ben Dussault, Mark Rawls, Cris Negron, Nader Yuson, and Tim Sprowl, some working directly on more theoretical mathematical projects and/or making hand calculations. There were also two visiting undergraduates from Cambridge University in this period, Tristan Kalloniatis and Gus Lonergan, whose work was in this more theoretical spirit. Both visited UVa during the summer break with the specific intent on working with me on this project. Tristan visited first, in a kind of lucky accident (a communication to our Department from a friend of his family, a UVa biologist), but his visit was so successful that Gus followed, and came back a second summer. Let me mention here that most of the UVa students have gone on to graduate programs or successful professional positions, and that Negron and Rawls were recipients of the McShane prize, the Department’s highest undergraduate award. Rawls's work, toward parallelizing Kazhdan-Lusztig polynomial calculations, is mentioned briefly in [80] and in more fully in lectures I have given. It plays a background role, along with an older serial program of McDowell, to more modern approaches [104] of myself and my recently graduated student, Tim Sprowl.

Going back to the 90’s the first goals were to check the Lusztig conjecture for the finite groups and Lie algebras of 5 x 5 matrices ("type A4") over the finite fields of 5 and 7 elements, respectively. To do this, one had to understand further huge matrix representations of these smaller systems, already as large as 10,000,000 x 10,000,000 in the case of the field of 5 elements, and 300,000,000 x 300,000,000 in the p=7 case. Brute force computing was out of the question, and the problems were barely accessible by using all available theory. A key ingredient was a series of hand calculations of Konikoff, giving essentially explicit multiplication tables for the action of the type A4 Lie algebra generators on the modules involved. (In more recent work, Kalloniatis has obtained a similar table for the Lie algebra of type G2.) This enabled computer calculations hundreds of times faster than the state of the art at the time. The Lusztig conjecture was checked in type A4 for p=5 and p=7. The p=5 case was done independently and somewhat earlier by a Danish team Lauritzen and Buch, but our calculation of the p=7 case has not been matched, even today, with computers so much faster. For p=5 we were the first to note that the calculations supported a stronger formulation of the Lusztig conjecture due to Kato. (According to a preprint posted by Williamson, however, both formulations fail for infinitely many primes. See the discussion in "Research Goals" on this web site.)

The debugging process in the work with Konikoff was incredibly formidable. What do you do with code that runs successfully on matrices that are smaller than 100 by 100, but then begins to go wrong? Check it by hand in the 100 by 100 case? Hardly. The approach we used effectively was to write secondary programs independently performing some of the tasks of the first (with different algorithms), and compare results. This is time consuming, but has worked for us. Using two and sometimes three independent programs, we were both able to debug our programs and be confident in the answers (which, a priori, could have turned out negative as well as positive). One of those programs developed with Konikoff, yielded very interesting structural detail as it progressed, though it was far from the fastest program. The detail was a series of submodules, a "filtration" of the of the standard modules (so-called "Baby Verma modules," finite dimensional versions of the infinite dimensional Verma modules) which led to later theoretical advances [87], as noted above. Supercomputers were not needed (by us, though they were used in Denmark), but large memories (for the time) were essential. In the current phase, and currently focused on Kazhdan-Lusztig polynomials, the use of Linux clusters seem well suited to the new algorithms being developed.

I will return to Kazhdan-Lustig polynomials momentarilly, but first, proceeding chronologically let me report on another direction, in which calculations, by computer and by hand, have been used to empirically explore analogs of the Lusztig conjecture which might hold for smaller primes. A natural starting place is the Lie algebra G2, where naive analogs of the Lusztig conjecture are known to fail for p=3. The Lusztig conjecture itself is true for p =5, and gives formulas for all irreducible modules when p=7. Kato’s modification (which just asserts that Lusztig's formulas can be used for all irreducible modules with "restricted" high weights) gives similar answers for p=7. The prime p=5 is smaller than the Coxeter number of the G2 root system, so there is no Lusztig conjecture per se. However, though not quite folklore, it has been suggested that the p=5 character theory still behaves well. In particular one can propose that something like the (Kato version of) the Lusztig conjecture holds. Tristan Kallonaits has examined the p=5 case and made this precise: The "same formulas" for the (singular) principal block case for p=5 hold as for a "corresponding" singular block case for p=7, if formulations using corresponding generating reflections in the affine Weyl group are used. Character formulas for any singular p=7 case are obtainable (as suggested by Kato) from the character formula proposed by Lusztig. Kallonaitis went further, and showed that the p=5 principal block and the the aforementioned singular block for p=7 share structural features, such as the dimensions of homomorphisms between Baby Verma modules. Some details of his work may be found in the G2 links below.

Next, the work of Gus Lonergan focused on finding generators and relations for some of the basic algebras arising in the Lusztig conjecture. In particular, in preliminary calculations, he has found these for an algebra associated to the representation theory of the group of type A4 whose high weights are smaller or equal to some "restricted" weight. Essentially, his calculations work for all primes 3 or larger or in the root of unity quantum case. (It is not possible to explain all the terminology here for this quite sophisticated work, and the reader will need to consult, for instance, the standard 2003 textbook on algebraic groups by Jens Jantzen.) The aim was to get a nice form for such generators and relations that were in some way compatible with recursions in formulas for Kazhdan-Lusztig polynomials, and the "preliminary" label for the calculations only occurs because a conjectured Ext relation, that could provide an interpretation of part of the recursions, is assumed. It is also conjectured that the generators can be taken to be taken to be that of degree 1 elements ("quiver arrows") in a graded algebra with all relations occuring of degree 2 (the "quadratic property", a consequence of "Koszul" property). This is known to be true in the quantum case, and in a modified "forced graded" versions of the algebras in the char. p case, at least for this type A3 case and p at least 5. Gus did not assume this, but the Koszul property is exhibited by his answers, and much more. This includes the sought-after compatibility with the Kazhdan-Lusztig recursions, though this occurs partly by assumption. Gus has also checked that algebras with his given generators and relations do exist, without any unintended collapsing. I consider these results very promising, both for understanding Kazhdan-Lusztig polynomials, and for gaining deeper insights into the algebras which fundamentally make the Lusztig conjecture possible.

As mentioned above, Tim Sprowl (a now-graduated double major in Computer Science and Mathematics) worked on directly computing Kazhdan-Lusztig polynomials, with a previous program of McDowell and work of Rawls in the background. The work on Wall's conjecture mentioned above arose from running and, eventually making much more efficient, a program first written by McDowell. Very recently, however, Sprowl has, at my suggestion, implemented a new algorithm. It does not try to compute all Kazhdan-Lusztig polynomials of interest, but instead is able to focus to some extent on a single one that might be interesting (especially those associated to very large "restricted" weights). Though we discovered it in a different way, it can be viewed as an improvement and simplification of a 1990 algorithm of Deodhar, using in its recursion only a single "Kazhdan-Lusztig basis" element, and using more easily computable expressions, otherwise. There are promising opportunities for relatively easy parallelizations. Sprowl's program completed (late November, 2012) its first such "interesting" calculation in type A8 (corresponding to the degree 9 special linear group), producing a value of 36672 for a polynomial coefficient equal to a family of H1 dimensions. The choice of "interesting" is a variation on a guess made in the 2010 paper of Scott-Xi.A link to the computed polynomial is given below.) For experts, 36672=mu(w0,w0w) where w0 is the long word in the ordinary Weyl group, w is in the affine Weyl group, and the length of w0w is the sum 119=36+83 of the lengths of w0 and w. For the convenience of all readers, I list the (largest) values of H1 dimensions found so far for the SLn series (type A(n-1)) with coefficients in an irreducible module with restricted highest weight: Corresponding to SL2,SL3,SL4,SL5,SL6,SL7,SL8,SL9 the respective dimensions are 1,1,1,2,3,16,469,36672. (Up through SL8 the numbers given correspond to the largest relevant Kazhdan-Lusztig polynomial coefficients corresponding to restricted weights. Conceivably, there could be larger values for restricted weights in the SL9 case, but empirical evidence from smaller SLn cases makes it unlikely.) It may be possible to do a corresponding SL10 calulations (type A9) with implementation of enough parallelization. In the late 90s, A5 was as far as we could go. Work on the An series is particularly relevant to studying growth rates of the most important Kazhdan-Lusztig polynomial coefficients (such as those that played a role in the disproof of the Wall conjecture).

A preprint [104] by Scott and Sprowl has been prepared and posted publicly on the the mathematics arXiv.

Below are data links, identifiable as just to the right of a "bullet" symbol, for some of the undergraduate research described above.

Data links for SL5 (characteristic p type A4) and Kazhdan-Lusztig polynomials (parabolic, affine) for (affine parabolic) type A5 (Konichoff and McDowell):

The p=7 computer runs given were of a program designed to find irreducible modules as submodules of standard modules in the infinitesimal (restricted Lie algebra) case. The runs show the program finding a maximal vector inside the irreducible submodule, then generating the appropriate weight spaces. (Weights here are sometimes represented as linear combinations of so-called fundamental roots, rather than fundamental weights.) Programs finding quotient modules, and programs using bilinear form methods (the previous standard approach) have also been developed, though are not yet fully functional except for p=5. A rough estimate is that our programs are about 1000 times faster than previous methods. The speed is largely due to parametric computations, mostly done by Konikoff (by hand), of closed form Lie algebra enveloping algebra formulas. The Kazhdan-Lusztig polynomial calculations, which led to the information about small coefficients above, were largely carried out by McDowell.

Data links for the restricted Lie algebra of type G2 (work of Kalloniatis):

Data links for type A3 (char. p or pth root of unity SL4) quiver and relations (work of Lonergan, preliminary):

Data links for recent developments regarding Kazhdan-Lusztig polynomials (work of Tim Sprowl):