## Khot,Minzer,Safra on approximate sections of sheaves

Subhash Khot is giving a talk at Current Developments in Math this year and his talk has the intriguing phrase “Grassmann graph” in it so I thought I’d look up what it is and what he and his collaborators prove about it, and indeed it’s interesting! I’m just going to jot down something I learned from “Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion,” by Khot, Dor Minzer, and Muli Safra, in a way that makes it sound like something algebraic geometers might be interested in, which, indeed, I think they might be!

Suppose you have a sheaf F on a space, and the space has a covering U_1, .. U_N. The sheaf axiom says that if we have a family of sections s_i of F(U_i) such that s_i and s_j agree on $U_i \cap U_j$ for all i,j, then there is actually a global section s in F(X) which restricts to each s_i.

What if we only have an approximate section? That is: what if we have a family of s_i such that: if I select i and j uniformly at random, the probability that s_i and s_j agree on $U_i \cap U_j$ is bounded below by some p > 0. Call such a family a “p-section.” (You should take the view that this is really a family of problems with X changing and N growing, so that when I say p > 0 the content is that p is bounded away from some 0 uniformly in X,N.)

The question is then: Is an approximate section approximately a section?

(This is meant to recall the principle from additive number theory that an approximate subgroup is approximately a subgroup, as in e.g. Freiman-Rusza.)

That is: if s_1, .. s_N from a p-section, is there some actual section s in F(X) such that, for i chosen uniformly at random,

$\mathbf{Pr}(s | U_i) = s_i > p' > 0$

for some p’ depending only on p?

The case which turns out to be relevant to complexity theory is the Grassmann graph, which we can describe as follows: X is a k-dimensional vector space over F_2 and the U_i are the l-dimensional vector spaces for some integer l. But we do something slightly weird (which is what makes it the Grassmann graph, not the Grassmann simplicial complex) and declare that the only nonempty intersections are those where $U_i \cap U_j$ has dimension l-1. The sheaf is the one whose sections on U_i are the linear functions from U_i to F_2.

Speculation 1.7 in the linked paper is that an approximate section is approximately a section. This turns out not to be true! Because there are large sets of U_i whose intersection with the rest of X is smaller than you might expect. This makes sense: if X is a space which is connected but which is “almost a disjoint union of X_1 and X_2,” i.e. $X_1 \cup X_2 = X$ and $\latex X_1 \cap X_2$ involves very few of the U_i, then by choosing a section of F(X_1) and a section of F(X_2) independently you can get an approximate section which is unlikely to be approximated by any actual global section.

But the good news is that, in the case at hand, that ends up being the only problem. Khot-Minzer-Safra classify the “approximately disconnected” chunks of X (they are collections of l-dimensional subspaces containing a fixed subspace of small dimension and contained in a fixed subspace of small codimension) and show that any approximate section of F is approximated by a section on some such chunk; this is all that is needed to prove the “2-to-2 games conjecture” in complexity theory, which is their ultimate goal.

So I found all this quite striking! Do questions about approximate global sections being approximated by global sections appear elsewhere? (The question as phrased here is already a bit weird from an algebraic geometry point of view, since it seems to require that you have or impose a probability measure on your set of open patches, but maybe that’s natural in some cases?)

Tagged , , ,

## In which I stop by NYU and get categorified by Kazhdan

I had the good luck to be in New York on Friday when David Kazhdan gave an unscheduled lecture at NYU about categorification and representations of finite groups.  For people like me, who spend most of our days dismally uncategorified, the talk was a beautiful advertisement for categorification.

Actually, the first twenty minutes of the talk were apparently a beautiful advertisement for the Langlands program, but I got lost coming from the train and missed these.  As a result, I don’t know whether the results described below are due to Kazhdan, Kazhdan + collaborators, or someone else entirely.  And I missed some definitions — but I think I can transmit Kazhdan’s point even without knowing them.  You be the judge.

It went something like this:

Let G be a reductive split group over a finite field k and B a Borel. Then C[G(k)/B(k)] is a representation of G(k), each of whose irreducible constituents is a unipotent representation of G(k).  (Note:  the definition of “unipotent representation” is one that I missed but it comes from Deligne-Lusztig theory.)

When G = GL_n, all unipotent representations of G appear in C[G(k)/B(k)], so this procedure gives a very clean classification of unipotent representations — they are precisely the constituents of C[G(k)/B(k)].  Equivalently, they are the direct summands of the center of the Hecke algebra C[B(k) \G(k) / B(k)].  For more general G (e.g. Sp_6, E_8) this isn’t the case.  Some unipotent representations are missing from C[G(k)/B(k)]!

Where are they?

One category-level up, naturally.

(see what I did there?)

OK, so:  instead of C[B(k)\G(k)/B(k)], which is the algebra of B(k)-invariant functions on G(k)/B(k), let’s consider H, the category of B-invariant perverse l-adic sheaves on G/B.  (Update:  Ben Webster explained that I didn’t need to say “derived” here — Kazhdan was literally talking about the abelian category of perverse sheaves.)  This is supposed to be an algebra (H is for “Hecke”) and indeed we have a convolution, which makes H into a monoidal category.

Now all we have to do is compute the center of the category H.   And what we should mean by this is the Drinfeld center Z(H).  Just as the center of an algebra has more structure than the algebra structure — it is a commutative algebra! — the Drinfeld center of a monoidal category has more structure than a monoidal category — it is a braided monoidal category.  It’s Grothendieck Group K_0(Z(H)) (if you like, its decategorification) is just a plain old commutative algebra.

Now you might think that if you categorify C[B(k)\G(k)/B(k)], and then take the (Drinfeld) center, and then decategorify, you would get back the center of C[B(k)\G(k)/B(k)].

But you don’t!  You get something bigger — and the bigger algebra breaks up into direct summands which are naturally identified with the whole set of unipotent representations of G(k).

How can we get irreducible characters of G(k) out of Z(H)?  This is the function-sheaf correspondence —  for each object F of Z(H), and each point x of G(k), you get a number by evaluating the trace of Frobenius on the stalk of F at x.  This evidently yields a map from the Grothendieck group K_0(Z(H)) to characters of G(k).

To sum up:  the natural representation C[G(k)/B(k)] sometimes sees the whole unipotent representation theory of G(k), but sometimes doesn’t. When it doesn’t, it’s somewhat confusing to understand which representations it misses, and why.  But in Kazhdan’s view this is an artifact of working in the Grothendieck group of the thing instead of the thing itself, the monoidal category H, which, from its higher categorical perch, sees everything.

(I feel like the recent paper of Ben-Zvi, Francis and Nadler must have something to do with this post — experts?)