Gale and Koszul duality, together at last July 14, 2008

Posted by Ben Webster in category O, combinatorics, hyperplanes, mathematical physics, papers, the arXiv.

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 $\mathcal{C}(\mathcal{V})$ (or equivalently, an algebra) from a linear program $\mathcal{V}$ (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. $\mathcal{C}(\mathcal{V})$ 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 $\mathcal{C}(\mathcal{V})$ is $\mathcal{C}(\mathcal{V}^\vee)$, the category associated to the Gale dual $\mathcal{V}^\vee$ of $\mathcal{V}$.

Now, part of the data of a linear program is an “objective function” (which we’ll denote by $\xi$) and of bounds for the contraints (which will be encoded by a vector $\eta$).  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 $\mathcal C(\mathcal V)$ 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 $\mathcal{C}(\mathcal{V})$, which we conjecture to include the fundamental group of the space of generic choices of objective function.

While we hope to present some more motivated definitions in the future, let’s start with an explicit presentation of our algebra, just so we can see it’s nothing scary.

Remember that a linear program $\mathcal{V}$ consists of a real vector space $V$, a collection of n linear functions $f_i\colon V\to\mathbb{R}$, and a choice a pair of vectors $\xi, \eta\in \mathbb{R}^n$.

The dual $\mathcal{V}^\vee$ of a program replaces $V$ with its perpendicular under dot product in $\mathbb{R}^n$, and $\xi^\vee=-\eta, \eta^\vee=-\xi$.

We consider a sign vectors $\alpha \in \{\pm 1\}^n$.  We let $\Delta_\alpha=\{v\in V+\eta |\alpha_i f_i(v) \geq 0\}$ and $\Sigma_\alpha=\{v\in V | \alpha_i f_i(v) \geq 0\}$.

We call $\alpha$ bounded if for each $v\in \Sigma_{\alpha}$, we have $\xi(v)=\sum_{i} xi_i f_i(v)\leq 0$.

We call $\alpha$ feasible if the set $\Delta_\alpha$ is non-empty.

As we discussed, the duality theorem for linear programming implies that a sign vector is feasible for one program if and only if it is bounded for the dual.  In particular, the set of sign vectors which are bounded and feasible for $\mathcal{V}$ and for $\mathcal{V}^\vee$ coincide.  We will call this set $P$, and it will index the simple modules of our algebra.

Now, consider the quiver whose vertices are the set $F$ of feasible sign vectors for $\mathcal{V}$, with an edge connecting any two vectors which differ in a single place.  More visually, one can think of the vertices as attached to the chambers $\Delta_\alpha$, and the edges as connecting chambers adjacent across a single hyperplane.  We consider the path algebra of this quiver tensored with the algebra of polynomial functions on $V$, $\Pi\otimes \mathbb{R}[V]$.  Let $e_\alpha$ be the “lazy path” of length 0, which stays at $\alpha$, and if $\alpha$ and $\alpha'$ are feasible sign vectors which only differ in the ith place $p_{i,\alpha}$ is the path of length of two which begins at $\alpha$, changes the ith coordinate (i.e. crosses the ith hyperplane) to $\alpha'$ and goes back to $\alpha$.  The algebra of interest to us, which we will denote $\mathcal{A}(\mathcal{V})$, is a finite dimensional quotient of this path algebra, by the relations

• any two paths from $\alpha$ to $\beta$ of minimal length (i.e. one where the length is the same as the number of coordinates where the vectors differ) are equal.
• for each $\alpha$ and each hyperplane $H_i$ adjacent to $\alpha$, we have $p_{i,\alpha}\otimes 1=1\otimes f_i$, where $f_i$ is considered as an polynomial on $V$.
• for each unbounded $\alpha\in F\setminus P$, we have $e_\alpha=0$, i.e. any path passing through that vertex is 0.

The reader may wonder why we included the infeasible vertices at all, if we were going to just declare them to be 0; the answer is that we want relations of the first two types involving unbounded vertices.  Similarly, the inclusion of the factor of $\mathbb R[V]$ is unnecessary as long as the $f_i$ generate this algebra, but it simplifies the writing of the second type of relations.

The category $\mathcal{C}(\mathcal{V})$ is, by definition, the category of finite-dimensional representations of $\mathcal{A}(\mathcal{V})$.

By doing some clever combinatorics, one can prove that for Gale dual arrangements, these algebras are quadratic dual, and thus once one proves they are Koszul, they’ll be known to be Koszul dual.

Proving that these algebras are Koszul, and proving the derived equivalences is a slightly longer story, which I don’t think there’s time for that in a blog post.  You can read all about it in the paper.

Next time, I’ll try to show how these categories actually come from geometry.  While the paper linked above uses relatively little geometry, hypertoric varieties were in the forefront of our minds the whole time we were writing this paper, and they make it clear why anyone would ever have written down these algebras.

1. David Speyer - July 15, 2008

Ben, I’m confused. You write:

“[C]onsider the quiver whose vertices are the set $F$ of feasible sign vectors for $V$,”

but later you say

“for each infeasible $\alpha \in F \setminus P$, we have $e_{\alpha}=0$.”

I am guessing that, in the second clause, you want to say unbounded, not infeasible?

2. Ben Webster - July 15, 2008

Uh, yes, that’s right. Good catch. Fixed.

Sorry comments are closed for this entry