Association Schemes and Configurations in Real and Complex Space

Worcester Polytechnic Institute, Worcester MA

Investigators

Abstract

This project investigates combinatorial objects fundamental to various areas of communications, information theory, networks, and numerous topics in pure mathematics. The team, consisting of the Principal Investigator (PI) and a PhD student will study association schemes and configurations in real and complex space. The project is motivated by applications in the theory of error-correcting codes, cryptography, quantum information theory, knot theory, extremal networks, finite geometry and spherical and projective codes. Association schemes and related tools play a fundamental role in these and other areas, for example guiding us to the best known efficiency bounds for binary error-correcting block codes used in most digital communications devices. As digital technologies grow in scale and complexity, we see increasing need for algebraic tools of this sort that extract important structural information efficiently from data. The project's broader impacts include training of highly qualified personnel and outreach to students and teachers in local schools. Progress on association schemes over the past 50 years has been phenomenal, and the variety of new applications that the theory handles has increased with each passing decade. Yet some fundamental problems, regarding cometric association schemes for example, remain unresolved with few new ideas emerging until recently. This project explores powerful mathematical tools, ranging from algebraic geometry to algebraic topology, to forge a stronger and more versatile theory of association schemes that will be equipped to attack existing open questions - both theoretical and applied - as well as future challenges that are likely to be framed in this general combinatorial language. Specific problems to be attacked include: efficient description of the ideal of polynomials vanishing on the set of columns of the first primitive idempotent of a cometric scheme; constructions (via finite geometry and design theory) and bounds for systems of lines with few angles; bounds on efficiency parameters of association schemes and codes; determining the structure of additive completely regular error-correcting codes. The mathematical tools to be employed have mainly been developed by the algebraic combinatorics community, including linear-algebraic and ring-theoretic techniques, as well as zero-dimensional ideals in polynomial rings and discrete homotopy. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.