Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

February 1, 2014

An Emerging Pattern in Algebra and Topology I

Posted by Emily Riehl

At the Joint Mathematics Meetings in Baltimore, I saw Benson Farb deliver a joint invited address on representation stability, the above eponymous “emerging pattern.” He began this work in 2010 with Tom Church, then a PhD student at the University of Chicago. I’ve been a fan for a few years now, and Benson’s beautiful talk has inspired me to write a brief summary.

This post is divided in two parts. In Part I, I’ll tell you about the talk, which was largely accessible to anyone with an undergraduate math background. In Part II, I’ll say a bit about the technical details and write about more recent developments, joint also with Jordan Ellenberg, in which some categorical ideas enable a simplified conceptual understanding of the patterns that frequently arise in practice.

Configuration spaces and polynomials

The topological spaces we’ll consider are configuration spaces. Let MM be any topological space (typically a manifold) and write Conf n(M)\text{Conf}_n(M) for the space of ordered tuples of nn distinct points in MM. The space Conf n(M)\text{Conf}_n(M) has a natural free action by S nS_n, the symmetric group on nn elements, that simply permutes the labels. The space of orbits, (the colimit of this action) is denoted by Conf n(M)/S n\text{Conf}_n(M)/S_n and is the space of unordered tuples of nn distinct points in MM.

Configuration spaces are basic mathematical objects. For example

Conf n()/S n=Poly n()\text{Conf}_n(\mathbb{C})/S_n = \text{Poly}_n(\mathbb{C})

is the space of monic, degree nn, square-free polynomials. Here, the tuple of unordered points corresponds to the roots of the polynomial. The square-free condition guarantees that the roots are distinct. The spaces Poly n()\text{Poly}_n(\mathbb{C}) are algebraic varieties. For example:

Poly 2()={z 2+bz+cb 24c0}\text{Poly}_2(\mathbb{C}) = \{ z^2 + b z + c \mid b^2 - 4 c \neq 0\} Poly 3()={z 3+bz 2+cz+db 2c 24c 34b 3d27d 2+18bcd0}.\text{Poly}_3(\mathbb{C}) = \{ z^3 + b z^2 + c z + d \mid b^2 c^2 - 4 c^3 - 4 b^3 d - 27 d^2 + 18 b c d \neq 0\}.

There are many reasons to care about the topology of these spaces. Even basic questions, such as whether Conf n(M)\text{Conf}_n(M) is connected, can have non-trivial applications to robotics. (Aside: I hereby propose “configuration” as the collective noun for a group of robots.) Another point of interest is that a loop in the space Conf n()/S n\text{Conf}_n(\mathbb{C})/S_n defines a braid with nn-strands. Indeed, the fundamental group π 1(Conf n()/S n)\pi_1(\text{Conf}_n(\mathbb{C})/S_n) of endpoint-preserving homotopy classes of loops is the braid group on nn-strands.

It will be important in what follows for us to learn how to visualize this — the visualization is easiest if you replace \mathbb{C} with a small disk. Picture nn distinct points in the plane, perhaps each in a different color, but as we’re visualizing the space of unordered configurations, you don’t have to remember which point has which color. We’ll visualize a path in this space as a “movie” in which we can watch the points move around. Each “frame” is a point in the configuration space. If we stack all the frames on top of each other in a direction orthogonal to the disk, the ambient space is a cylinder. As the colored points move around, they trace strings from the top of the cylinder to the bottom. Because the points never collide, the strings never intersect. Hence, a loop defines a braid. A loop in the space of ordered configurations is called a pure braid, meaning that each strand starts and ends in the same relative position.

The fundamental problem is to understand the topology of the spaces of configurations of ordered and unordered points. A standard way to try to do this is to compute the cohomology of the space. It’s okay if you don’t know exactly what this means. The point is that to any topological space XX one can define a sequence of rational vector spaces H i(X;)H^i(X; \mathbb{Q}) for each i0i \geq 0. These algebraic invariants capture a significant portion of the topological information about the space. For fixed ii, our aim is to reduce infinitely many computations to finitely many by investigating how these vector spaces depend on nn.

Case study: first cohomology

Let us consider this problem for i=1i=1. Elements of H 1(Conf n();)H^1(\text{Conf}_n(\mathbb{C});\mathbb{Q}) are represented by homomorphisms ϕ:π 1(Conf n())\phi\colon\pi_1(\text{Conf}_n(\mathbb{C})) \to \mathbb{Q}. To define such a ϕ\phi, we must assign an algebraic invariant (a rational number) to each loop in Conf n()\text{Conf}_n(\mathbb{C}) in a natural way; here this means that the invariant must be additive with respect to concatenation of loops, so that the map ϕ\phi is a homomorphism.

One idea is to use the winding number. For each pair 1i,jn1 \leq i,j \leq n with iji \neq j, define ω ij:π 1(Conf n())\omega_{ij} \colon \pi_1(\text{Conf}_n(\mathbb{C})) \to \mathbb{Q} by

ω ij(α)=\omega_{ij}(\alpha) = winding number of jj around ii while performing α\alpha.

Note that ω ij=ω ji\omega_{ij}=\omega_{ji}. Benson described a beautiful intuition for this observation that he learned from his advisor, William Thurston, who always encouraged him to project himself into the space. Imagine ii and jj are dance partners holding hands. As they turn around the dance floor, ii performs one clockwise rotation each time jj does so and conversely.

Proposition. {ω ij1i<jn}\{\omega_{ij} \mid 1 \leq i \lt j \leq n \} is a linearly independent in H 1(Conf n())H^1(\text{Conf}_n(\mathbb{C})).

Linear independence is implied by the existence of loops that produce a non-trivial winding number for some pair (i,j)(i,j) while fixing the remaining points. Moreover:

Theorem (Arnol’d 1968). H 1(Conf n();)H^1(\text{Conf}_n(\mathbb{C});\mathbb{Q}) is spanned by {ω ij1i<jn}\{\omega_{ij} \mid 1 \leq i \lt j \leq n \}. Hence H 1(Conf n();) (n 2)H^1(\text{Conf}_n(\mathbb{C});\mathbb{Q}) \cong \mathbb{Q}^{\left(\begin{array}{c} n \\ 2 \end{array}\right)}.

This is exactly the sort of closed form we might hope for. This leads to the next question:

Question: What is H 1(Conf n()/S n;)=H 1(Poly n();)H^1(\text{Conf}_n(\mathbb{C})/S_n; \mathbb{Q}) = H^1(\text{Poly}_n(\mathbb{C});\mathbb{Q})?

As before, we seek a numerical invariant for loops of unordered configurations. One such invariant is the total winding number

α\alpha \mapsto total winding number of α= ijω ij(α).\alpha = \sum_{i \neq j} \omega_{ij}(\alpha).

It turns out this is the only invariant.

Corollary. H 1(Poly n)={H^1(\text{Poly}_n) \cong \mathbb{Q} = \mathbb{Q}\{total winding number}\}.

Proof: H 1(Poly n)=H 1(Conf()/S n)H^1(\text{Poly}_n) = H^1(\text{Conf}(\mathbb{C})/S_n) = S nS_n-fixed vectors in H 1(Conf n())H^1(\text{Conf}_n(\mathbb{C})) = \mathbb{Q}-span of the total winding number. \square

Homological stability

More generally:

Theorem (Arnol’d 1968, F Cohen 1972). For any i0i \geq 0, H i(Poly n)H^i(\text{Poly}_n) does not depend on nn for nin \geq i.

This theorem implies that the spaces Poly n\text{Poly}_n satisfy homological stability. While configurations of unordered points satisfy homological stability, configurations of ordered points do not. In fact, for each ii

dimH i(Conf n()),n.\dim H^i(\text{Conf}_n(\mathbb{C})) \to \infty, n \to \infty.

The reason that homological stability always fails for the spaces of ordered configurations has to do with representation theory. Because the symmetric group S nS_n acts on Conf n()\text{Conf}_n(\mathbb{C}), S nS_n also acts on the vector space H i(Conf n())H^i(\text{Conf}_n(\mathbb{C})).

A fact from representation theory is that (except for n=4n=4) any vector space that admits a non-trivial S nS_n action must have dimension at least n1n-1. (Technically this is only true if I can also exclude alternating representations. Exercise: prove that H 1(Conf n())H^1(\text{Conf}_n(\mathbb{C})) does not contain any alternating representations.) In particular

dimH i(Conf n()),n\dim H^i(\text{Conf}_n(\mathbb{C})) \to \infty, n \to \infty

and homological stability always fails. But somehow homological stability should hold morally. For example, up to permuting indices, there’s only one ω ijH 1(Conf n())\omega_{ij} \in H^1(\text{Conf}_n(\mathbb{C})). A more precise statement is that each H 1(Conf n())H^1(\text{Conf}_n(\mathbb{C})) is the same representation of nn. From the basis described in Arnol’d’s theorem above, it is just the representation where S nS_n acts in the expected way on unordered pairs of distinct elements of nn.

Representation theory of the symmetric groups

Here is a quick primer on representation theory. A representation is a \mathbb{Q}-vector space with a linear group action, or, equivalently, a functor from the one-object groupoid whose morphisms correspond to group elements to the category Vec \mathbf{Vec}_{\mathbb{Q}}. A representation is irreducible if it has no invariant subspaces. By Maschke’s theorem, every representation decomposes into a direct sum of irreducibles. Thus, the goals of representation theory are to:

classify all the irreducible representations of a given group

understand how to decompose a given representation into irreducibles

Here, we’re interested in representations of symmetric groups, for which we have the following beautiful theorem.

Theorem (Young 1900). Irreducible representations of S nS_n correspond to partitions of nn.

For example:

The trivial representation of S nS_n corresponds to the partition nn.

The standard representation of S nS_n (the orthogonal complement of the fixed vector in the permutation representation of S nS_n on n\mathbb{Q}^n) corresponds to the partition (n1)+1(n-1)+1.

We want notation for irreducible representations that is independent of nn. For this, we denote the irreducible representation of S nS_n corresponding to the partition

(n5)+3+1+1(n-5) + 3 + 1 + 1

of nn by V(3,1,1)V(3,1,1). So V(0)V(0) is the trivial representation, and V(1)V(1) is the standard representation.

Representation stability?

Maschke’s theorem says that

H i(Conf n())= partitionsλV(λ) c n,λH^i(\text{Conf}_n(\mathbb{C})) = \oplus_{\text{partitions} \lambda} V(\lambda)^{c_{n,\lambda}} for some indices c n,λc_{n,\lambda}. The main problem is to find the c n,λc_{n,\lambda}.

Example. H 1(Conf n())=V(0)V(1)V(2)H^1(\text{Conf}_n(\mathbb{C})) = V(0) \oplus V(1) \oplus V(2) for all n3n \geq 3. Here the trivial representation V(0)V(0) is the collection of fixed vectors, the span of the total winding number. The subspace V(0)V(1)V(0) \oplus V(1) is the permutation representation of some collection of basis vectors {u 1,,u n}\{u_1,\ldots, u_n\} of H 1(Conf n())H^1(\text{Conf}_n(\mathbb{C})). These basis vectors have geometric meaning: u i(α)u_i(\alpha) is the total winding of the loop α\alpha around the point ii.

This example implies that first cohomology of ordered configuration spaces is representation stable: the index c n,λc_{n,\lambda} of the irreducible representation λ\lambda is independent of nn for nn sufficiently large. Tom and Benson wondered whether this phenomenon would also occur for the higher cohomology groups. They recruited David Hemmer to compute H 2(Conf n())H^2(\text{Conf}_n(\mathbb{C})) for low nn. Unfortunately, his calculations, aided by some computer algebra package whose name I didn’t catch, did not stabilize. But thinking this theory was too beautiful not to be true, Benson pressed him to try again, and it turned out that there was a bug in the software, relating to a failure to account for the outer automorphism of S 6S_6. Once this was corrected, Hemmer calculated that the second cohomology groups appear to stabilize for n8n \geq 8.

This lead to the following result:

Theorem (Church-Farb 2010). Fix i0i \geq 0. Then H i(Conf n())= partitionsλV(λ) c n,λH^i(\text{Conf}_n(\mathbb{C})) = \oplus_{\text{partitions} \lambda} V(\lambda)^{c_{n,\lambda}} and c n,λc_{n,\lambda} does not depend on nn for n4in \geq 4i.

Applications

Now it turns out that the stable representations are quite complicated. See their paper. But nevertheless, this stability phenomenon has led to useful computations with numerous practical applications. I’ll mention just one: to combinatorial statistics for polynomials over a finite field 𝔽 q\mathbb{F}_q. More details can be found in this paper, joint with Jordan Ellenberg.

By the Grothendieck-Lefschetz theorem, the multiplicity of a given irreducible representation in H i(Conf n())H^i(\text{Conf}_n(\mathbb{C})) corresponds to a point count in the variety Poly n(𝔽 q)\text{Poly}_n(\mathbb{F}_q) weighted by the character of the representation, and this correspondence is linear. Thus each index encodes some “statistic” for monic, square-free polynomials over 𝔽 q\mathbb{F}_q. Representation stability implies that these statistics are asymptotically stable.

For example:

The multiplicity of the trivial representation V(0)V(0) corresponds to the number of degree nn square-free polynomials, which is q nq n1q^n - q^{n-1}.

The multiplicity of the standard representation V(1)V(1) corresponds to the expected number of linear factors, which is 11q+1q 2±1q n21 - \frac{1}{q} + \frac{1}{q^2} - \cdots \pm \frac{1}{q^{n-2}}.

Posted at February 1, 2014 1:32 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2690

2 Comments & 0 Trackbacks

Re: An Emerging Pattern in Algebra and Topology I

Just to clarify there was no bug in the software, there was just me mislabeling a character table that had been permuted by the outer automorphism of S6, so I had the labeling of the irreducles wrong.

Also once I pushed past this I did actually prove the stability not just compute some larger examples!

Posted by: David Hemmer on March 7, 2014 6:38 PM | Permalink | Reply to this

Re: An Emerging Pattern in Algebra and Topology I

Thanks for writing to correct the record. That part of the talk went rather quickly and I suspected I didn’t remember it perfectly. Now that you mention it, I think Benson did give you credit for the stability result. My apologies!

Posted by: Emily Riehl on March 7, 2014 9:51 PM | Permalink | Reply to this

Post a New Comment