Gale and Koszul duality, together at last

So, in past posts, I’ve attempted to explain a bit about Gale duality and about Koszul duality, so now I feel like I should try to explain what they have to do with each other, since I (and some other people) just posted a preprint called “Gale duality and Koszul duality” to the arXiv.

The short version is this: we describe a way of getting a category  (or equivalently, an algebra) from a linear program (or as we call it, a polarized hyperplane arrangement).

Before describing the construction of this category, let me tell you some of the properties that make it appealing.

Theorem. is Koszul (that is, it can be given a grading for which the induced grading on the Ext-algebra of the simples matches the homological grading).

In fact, this category satisfies a somewhat stronger property: it is standard Koszul (as defined by Ágoston, Dlab and Lukács.  Those of you with Springer access can get the paper here).  In short, the category has a special set of objects called “standard modules” (which you should think of as analogous to Verma modules) which make it a “highest weight category,”  such that these modules are sent by Koszul duality to a set of standards for the Koszul dual.

Of course, whenever confronted with a Koszul category, we immediately ask ourselves what its Koszul dual is.  In our case, there is a rather nice answer.

Theorem. The Koszul dual to is , the category associated to the Gale dual of .

Now, part of the data of a linear program is an “objective function” (which we’ll denote by ) and of bounds for the contraints (which will be encoded by a vector ).  Stripping these way, we end up with a vector arrangement, simply a choice of a set of vectors in a vector space, which will specify the constraints.

Theorem. If two linear programs have same underlying vector arrangment, the categories may not be equivalent, but they will be derived equivalent, that is, their bounded derived categories will be equivalent.

Interestingly, these equivalences are far from being canonical. In the course of their construction, one actually obtains a large group of auto-equivalences acting on the derived category of , which we conjecture to include the fundamental group of the space of generic choices of objective function.

Gale duality and linear programing.

So, I felt I should try to explain a bit about this hypertoric stuff. I think the first order of business should be explaining what Gale duality is. This is all “just” linear algebra, in principle very simple, though not exactly the usual perspective on these things. To slightly paraphrase some notes from Daniel Kleitman’s website:

The act of writing down explicit dual equations of a given hyperplane arrangement is not complicated but it is quite unnatural to human beings. You can expect to do it hesitantly and incorrectly the first three times you try to do it.