Configuration spaces of manifolds with flows (with John Wiltshire-Gordon)

New preprint up on the arXiv:  “Algebraic structures on cohomology of configuration spaces of manifolds with flows,” a short paper joint with John Wiltshire-Gordon.

John is a student at Michigan, finishing his Ph.D. this year under David Speyer, and he’s been thinking about stuff related to FI-modules ever since his undergrad days at Chicago hanging out with Benson Farb.

But this paper isn’t actually about FI-modules!  Let me explain.  Here’s the motivating question.  When M is a manifold, and S a finite set, we denote by PConf^S M the pure configuration space of M, i.e. the space of injections from S to M.  If S is the set 1,…,n we write PConf^n M for short.

Question:  Let M be a manifold.  What natural algebraic structure is carried by the cohomology groups H^i(PConf^n M,Z)?

Here’s one structure.  If is an injection, composition yields a map from PConf^T M to PConf^S M, which i turn yields a map from H^i(PConf^S M, Z) to  H^i(PConf^T M, Z).  In other words,

is a functor from the category of finite sets with injections to the category of k-vector spaces.  Such a functor is called an FI-module over k.  A big chunk of my paper with Benson Farb and Tom Church is devoted to figuring out what consequences this structure has for the Betti numbers, and it was by these means that Tom first proved that the unordered configuration spaces have stable cohomology with rational coefficients.  (This is actually false with integral coefficients, or when the coefficient field has characteristic p, but see the beautiful theorem of Rohit Nagpal for the story about what happens in the latter case.  How have I not blogged about that already?)

So it turns out that H_i(PConf M) is a finitely generated FI-module (the definition is what you expect) and this implies that the Betti number h^i(PConf^n M) agrees with some polynomial P_i(n) for all sufficiently large n.  For example, H_1(PConf^n S^2) has dimension

(1/2)n(n-3)

for n >= 3, but not for n=0,1,2.

If you know a little more about the manifold, you can do better.  For instance, if M has a boundary component, the Betti number agrees with P_i(n) for all n.  Why?  Because there’s more algebraic structure.  You can map from PConf^T to PConf^S, above, by “forgetting” points, but you can also add points in some predetermined contractible neighborhood of the boundary.  The operation of sticking on a point * gives you a map from PConf^S to PConf^{S union *}.  (Careful, though — if you want these maps to compose nicely, you have to say all this a little more carefully, and you really only want to think of these maps as defined up to homotopy; perfectly safe as long as we’re only keeping track of the induced maps on H^i.)

We thought we had a pretty nice story:  closed manifolds have configuration spaces with eventually polynomial Betti numbers, manifolds with boundary have configuration spaces with polynomial Betti numbers on the nose.  But in practice, it seems that configuration spaces sometimes have more stability than our results guaranteed!  For instance, H_1(PConf^n S^3) has dimension

(1/2)(n-1)(n-2)

for all n>0.  And in fact EVERY Betti number of the pure configuration space of S^3 agrees with a polynomial P_i(n) for all n > 0; the results of CEF guarantee only that h^i agrees with a polynomial once n > i.

What’s going on?

In the new paper, John and I write about a different way to get “point-adding maps” on configuration space.  If your M has the good taste to have an everywhere non-vanishing vector field, you can take any one of your marked points x in M and “split it” into two points y and y’, each very near x along the flowline of the vector field, one on either side of x.  Now once again we can both add and subtract points, as in the case of open manifolds, and again this supplies the configuration spaces with a richer structure.  In fact (exercise!) H_i(PConf^n M) now carries an action of the category of noncommutative finite sets:  objects are finite sets, morphisms are set maps endowed with an ordering of each fiber.

And fortunately, John already knew a lot about the representation theory of this category and categories like it!  In particular, it follows almost immediately that, when M is a closed manifold with a vector field (like S^3) the Betti number h^i(PConf^n M) agrees with some polynomial P_i(n) for all n > 0.  (For fans of character polynomials, the character polynomial version of this holds too, for cohomology with rational coefficients.)

That’s the main idea, but there’s more stuff in the paper, including a very beautiful picture that John made which explains how to answer the question “what structure is carried by the cohomology of pure configuration space of M when M has k nonvanishing vector fields?”  The answer is FI for k=0, the category of noncommutative finite sets for k=1, and the usual category of finite sets for k > 1.

The braid group, analytic number theory, and Weil’s three columns

This post is about a new paper of mine with Akshay Venkatesh and Craig Westerland; but I’m not going to mention that paper in the post. Instead, I want to explain why topological theorems about the stable homology of moduli spaces are relevant to analytic number theory.  If you’ve seen me give a talk about this stuff, you’ve probably heard this spiel before.

We start with Weil’s famous quote about “the three columns”:

“The mathematician who studies these problems has the impression of deciphering a trilingual inscription. In the first column one finds the classical Riemannian theory of algebraic functions. The third column is the arithmetic theory of algebraic numbers.  The column in the middle is the most recently discovered one; it consists of the theory of algebraic functions over finite fields. These texts are the only source of knowledge about the languages in which they are written; in each column, we understand only fragments.”

Let’s see how a classical question of analytic number theory works in Weil’s three languages.  Start with the integers, and ask:  how many of the integers between X and 2X are squarefree?  This is easy:  we have an asymptotic answer of the form

(In fact, the best known error term is on order X^{17/54}, and the correct error term is conjectured to be X^{1/4}; see Pappalardi’s “Survey on k-freeness” for more on such questions.)

So far so good.  Now let’s apply the popular analogy between number fields and function fields, going over to Weil’s column 3, and ask: what’s the analogous statement when Z is replaced by F_q[T]?

Disks in a box, update

In April, I blogged about the space of small disks in a box.  One question I mentioned there was the following:  if C(n,r) is the space of configurations of n non-overlapping disks of radius r in a box of sidelength 1, what kind of upper bounds on r assure that C(n,r) is connected?  A recent preprint of Matthew Kahle gives some insight into this question: he produces configurations of disks which are stable (each disk is hemmed in by its neighbors) with r on order of 1/n.  (In particular, the density of such configurations goes to 0 as n goes to infinity.)  Note that Kahle’s configurations are not obviously isolated points in C(n,r); it could be, and Kahle suggests it is likely to be, that his configurations can be deformed by moving several disks at once.

Also appearing in Kahle’s paper is the stable 5-disk configuration at left; this one is in fact an isolated point in C(5,r).

More Kahle: another recent paper, with Babson and Hoffman, features the theorem that a random 2-complex on n vertices, where the edges are all present and each 2-face appears with probability p, transitions from non-simply-connected to simply connected when p crosses n^{-1/2}.  This is in sharp contrast with the H_1 of the complex with Z/ ell Z coefficients, which disappears almost surely once p exceeds 2 log n / n, by a result of Meshulam and Wallach.  So in some huge range, the fundamental group is almost surely a big group with no nontrivial abelian quotient!  (I guess this doesn’t formally follow from Meshulam-Wallach unless you have some reasonable uniformity in ell…)

One naturally wonders:  Let pi_1(n,p) be the fundamental group of a random 2-complex on n vertices with facial probability p.   If G is a finite simple group, what is the expected number of surjections from pi_1(n,p) to G?  Does it sharply transition from nonzero to zero?  Is there a range of p in which pi_1(n,p) is almost certainly an infinite group with no finite quotients?

Anabelian puzzle 4: What is the probability that a set of n points has no 3 collinear?

OK, this isn’t really an anabelian puzzle, but it was presented to me at the anabelian conference by Alexei Skorobogatov.

Let X_n be the moduli space of n-tuples of points in A^2 such that no three are collinear.  The comment section of this blog computed the number of components of X_n(R) back in January.  Skorobogatov asked what I could say about the cohomology of X_n(C).  Well, not a lot!  But if I were going to make a good guess, I’d start by trying to estimate the number of points on X_n over a finite field F_q.

So here’s a question:  can you estimate the number of degree-n 0-dimensional subschemes S of A^2/F_q which have no three points collinear?  It seems very likely to me that the answer is of the form

for some power series P.

One way to start, based on the strategy in Poonen’s Bertini paper:  given a line L, work out the probability P_L that S doesn’t have three points on L.  Now your first instinct might be to take the product of P_L over all lines in A^2; this will be some version of a special value of the zeta function of the dual P^2.  But it’s not totally clear to me that “having three points on L_1” and “having three points on L_2” are independent.

Hard discs, configuration spaces, kissing spheres, the 15 puzzle

Persi Diaconis has a lovely article in this month’s Bulletin of the AMS about the “Markov chain Monte Carlo revolution.”  I especially liked the discussion of the “hard disk model” for fluids, which was new to me.  Suppose X is a region in the plane and r a small positive number; then we can denote by Conf(X,n,r) the subspace of X^n consisting of n-tuples (x_1, … x_n) such that the discs of radius r centered at the x_i don’t intersect.  A natural statistic on Conf(X,n,r) is the “packing density”

the proportion of the area of X which is taken up by the discs.  You can imagine Conf(X,n,r) as a model for the space of states of a substance whose molecules are represented by the discs — the molecules are forbidden to overlap, but are otherwise allowed to move freely.  When is small, the space looks a lot like Conf(X,n,0), the configuration space of n distinct points in R.  But when is large (more than about .71) the system undergoes a “Kirkwood phase transition” and the balls are constrained to look something like a lattice packing.  You might think of the former case as modeling a liquid, and the latter as modeling a solid.  See Figure 5 of Persi’s paper for a nice illustration of this phenomenon.

Apparently, we don’t know very much about the topology of Conf(X,n,r).  Of course, for very large r the configuration space is empty.  When r = 0 it is the usual configuration space of n distinct points on X.  You might imagine carrying out a kind of Morse-theoretic decomposition of Conf(X,n,0) as follows:  for each n-tuple (x_1, … x_n) of distinct points on X, write

where d(x,x’) is the distance between points x and x’ of X.  Then f seems a bit like a Morse function, and you can imagine building up Conf(X,n,0) by starting with a $0$-cell at each local minimum of f, then attaching 1-cells for each critical point with one negative eigenvalue, and so on.  Of course, f is badly non-smooth!  But you can imagine, I guess, replacing the maximum by an for suitably large p and seeing what happens…

The most primitive topological question you can ask is whether Conf(X,n,r) is connected — that is, given two configurations of n hard r-discs in X, is there always room to move from one configuration to the other?

One special case of this question is, to my eye, particularly charming: given a configuration of discs, can you permute the discs arbitrarily?  When the discs are packed almost as tightly as possible, you might expect a negative answer; but in practice, it seems that a very small amount of wiggle room is enough to re-order the discs any way you want.

Example 1:  Suppose X is a unit sphere and r is pi/6 radians.  Then a configuration of n disjoint r-discs on X is equivalent to a configuration of n disjoint unit spheres tangent to X.  The “kissing spheres problem,” which goes back at least to Newton, asks:  what is the maximal number of disjoint unit spheres that can be tangent to X?  The answer is 12; for instance, one can arrange these spheres at the vertices of a regular icosahedron.  This leaves a little room for the spheres to roll around; and it turns out that this small leeway is enough to allow one to permute the spheres by an arbitrary element of S_12!  John Baez has a nice discussion of this in a very early episode of This Week’s Finds.

Example 2: Let X be a unit square, and take r = 1/8 and n = 15; then you can cut X into 16 squares of sidelength 1/2, and place a disc at the center of all the squares but the one in the lower left corner.  (In the interest of writing this post quickly, I’ll leave you to draw your own picture of this.)  Now this packing of discs is pretty tight — at the outset, only two of the discs have room to move.  But it turns out that here, too, one can permute the discs in an almost arbitrary way; you can get any permutation in the alternating group A_15.  In fact, this problem is nothing but a continuous version of the Sam Loyd “15” puzzle.

If you wanted to get a general sense of what was going on here, you might discretize the problem in the following way:  suppose X is a graph with N vertices, n of which are covered by stones.  You are allowed to move any stone to an adjacent empty vertex.  Can you permute the stones in any way you like?  If N = n, the answer is clearly no; there are no allowable rooms.  But if you allow any wiggle room at all — that is, if you let n = N-1 — the answer, somewhat suprisingly to me, is essentially yes.  This is a theorem of Wilson (“Graph Puzzles, Homotopy, the Alternating Group”) from 1974:  if a graph X cannot be made disconnected by the removal of a singular vertex, and is not an N-cycle, then the N-1 stones can be permuted by any permutation in the alternating group, with one exception when N = 7.

What is this strange exceptional 7-vertex graph?  See if you can figure it out!  Or look here.

Blogging my orphans: n points in the plane with no three collinear

“Orphans” are things you meant to think about but which you’ve regretfully concluded are never going to rise to the top of the stack. Ideas you never finished having.

Blogging your orphans seems a good use of a math blog, or even a partial math blog like this one — at best, someone else will be able to tell you what’s interesting about your question, or even derive some interest from it themselves; and at worst, someone will be able to explain to you why your question is in fact not interesting, thus setting your mind at ease.

Anyway: the mention of Voronoi cells reminded me of a question that once vexed me about combinatorial geometry in R^2. The question actually arose from an article I wrote about Howard Rosenthal and Keith Poole, political scientists who use data from Congressional votes to map legislators onto low-dimensional Euclidean space. But their method doesn’t really specify points in R^n. When n = 1, for instance, what they get is not a set of 535 points on the real line, but an ordering of the 535 legislators along an axis representing liberalism at one end and conservatism at the other.

What’s really being recorded by the projection of Congress to R^2? I think it’s something like this — for each triple of legislators (x,y,z) you ask: is z to the left or the right of the ray that starts at x and proceeds towards y?

There are n! possible orderings of n points on the line. How many “orderings” are there of n points in the plane?

An algebraic combinatorist might phrase the question like this: Let M be a 3xn matrix with real entries, where the third column consists entirely of 1’s. Suppose every 3×3 minor of M is nonsingular. Then let f(M) be a function from the set of 3-tuples of distinct elements of [1..n] to the set {+1,-1}, where you assign to each 3-tuple (i,j,k) with i < j < k the sign of the determinant of the 3×3 matrix formed by rows i,j,k of M.

Question: As M ranges over 3xn matrices of the given form, how many different functions f(M) are there?

An obvious upper bound is 2^(n choose 3), but this is way too big. Note that if you replace “3” by “2”, the answer to the analogous question is n!.

As a geometer, I’d phrase the question in a different (but I think equivalent) way:

Question: Let X_n be the space of ordered n-tuples of points in R^2 such that no three points are collinear. How many components does X_n have?

Again, if you replace R^2 with R^1 and “no three points are collinear” with “no two points coincide,” you get n!.

Let a(n) be the answer to the questions above (which, if I am not confused, have the same answer.) Then a(3) = 2 and a(4) = 14, and I think maybe a(5) is 252 but I’m not really sure. Combinatorial geometers with a soft spot for orphans, tell me more!