Equidistribution with moving targets

Tom Church, Benson Farb and I have a new paper about FI-modules on the arXiv.  This one concerns a family of questions we were thinking about at the very beginning of the project, and which we now have enough tools to talk about properly.

The paper is in some measure expository —  many or perhaps most of the results we talk about can be proved by other means.  But setting things up in FI-module language expresses everything in a nice uniform way.

Here’s one way to think about what’s going on.   Suppose you let P(q,n) be the probability that a monic squarefree polynomial over F_q is irreducible.  Now you can work out a closed formula for this number, but I want you to strike that from your mind for a second, because that’s not what I want to think about.

Each squarefree polynomial f of degree n has a partition of n attached to it; namely, the one that breaks n up into the degrees of the irreducible factors of q.  Another view:  if we let Y_n be the space of ordered n-tuples of distinct points in A^1 (i.e. the complement of the fat diagonals in A^n) then Y_n carries a natural action of S_n, and the quotient, which we’ll call X_n, is nothing more than the space of monic squarefree polynomials:  the map is

(z_1, .. z_n) -> (x-z_1)…(x-z_n).

So every monic squarefree over F_q, i.e. every point of X_n(F_q), induces a Frobenius element of Gal(Y_n/X_n) = S_n, at least up to conjugacy, and this conjugacy class of S_n is the one whose cycle type is the partition described above.

So for each q we get a set of |X_n(F_q)| = q^n – q^{n-1} elements of S_n, or at least elements up to conjugacy.  And if we let q vary over larger and larger powers of a prime p, we get an infinite sequence of elements of S_n, and the Weil conjectures tell us that these elements become equidistributed in S_n.  In particular, the chance that they are n-cycles (i.e. the chance that f is irreducible) is just the proportion of S_n taken up by n-cycles, which is 1/n.  And that is why P(q,n)/{q^n – q^{n-1}) converges to 1/n as q goes up.

But what if n goes up with q fixed?  We still have an infinite sequence of permutations

g_1, g_2, g_3, …

(really, permutations defined up to conjugacy) but now the permutations are getting larger and larger, with only finitely many landing in any particular S_n!  So here’s the question:  what, if anything, can it mean to say that these elements are equidistributed, when there’s no fixed group for them to equidistribute in?  In other words, what is equidistribution with moving targets?

Here’s one thing you might mean.  Let X_k be the class function on S_n sending each permutation to the number of k-cycles in its cycle decomposition.  When g is a random element of S_n for n large, X_k is more or less a Poisson variable with mean 1/k.  So as a kind of consequence of “equidistribution with moving targets” one might ask that

$\lim_{n \ra \infty} 1/n \sum_{i=1}^n X_k(g_i) = 1/k$.

Makes sense, right?  We have as a slogan “A random permutation has 1 fixed point,” without reference to the size of the set being permuted; so if the sequence g_i is to be called “equidistributed” in any sense, the average number of fixed points of g_i should be 1.

In fact, if P is any polynomial in the X_i, the mean of P on S_n approaches a limit a(P) as n grows, and so one might ask more generally that the average of the P(g_i) approaches a(P).

Now it turns out that the g_i coming from squarefree polynomials don’t have this property.  For instance, the average number of fixed points of g_i — that is, the average number of linear factors of a squarefree polynomial — is q/(q+1), not 1.  But at least that limit exists!  And as q goes to infinity, the limit goes to 1, so at least the sequence is in some sense closer and closer to being “equidistributed” as q grows.

ANYWAY:  The point of the linked paper is to show that this kind of behavior is quite general for sequences of permutations coming from (sequences of) moduli spaces whose cohomology groups form finitely generated FI-modules.  The two motivating examples are:

  • decomposition into irreducible factors of random squarefree degree-n polynomials over F_q;
  • decomposition into F_q-rational tori of random tori in GL_n(F_q).

And we show that these two sequences of (conjugacy classes of) permutations both “approximately equidistribute” in the sense sketched above.  The actual limits are different, though!  For instance, the average number of rational 1-dimensional tori is not 1, and not q/(q+1), but q/(q-1).  And you can also, in a fairly uniform way, generate asymptotics for how often the partition has only one part, how often it has no small parts, etc.  Most of the actual facts we assert about these sequences are known, or knowable, by existing means; but the point is to observe that they are true for the same reason in both cases, and that the precise limits can be read off the structure of some finitely-generated FI module of interest.

4 thoughts on “Equidistribution with moving targets

  1. Qiaochu Yuan says:

    Cool! This is probably elementary, but I don’t understand how “…every monic squarefree over F_q, i.e. every point of X_n(F_q), induces a Frobenius element of Gal(Y_n/X_n) = S_n, at least up to conjugacy.” I have some idea of how this works for the ring of integers of a number field but this seems much more general.

  2. JSE says:

    I was probably being too quick (result of wanting to blog about this paper in a timely way but having many other pressing deadlines…) This is a general fact about etale covers — if Y/X is a G-cover, each point of X(F_q) gives a G-cover of Spec F_q by pulling back the map Spec F_q -> X, and these are classified by conjugacy classes of maps Gal(F_q) -> G; since Gal(F_q) is cyclic, this is basically just to specify an element of G (in this case, S_n) up to conjugacy.

  3. David Speyer says:

    A more concrete answer: Let Y/X be a G-cover. Let x be an F_q point of X; let its preimage in Y(\bar{\mathbb{F}}_q) be y_1, y_2, …, y_g (where g=|G|). The G-action on Y is free and transitive on the orbit y_1, y_2, …, y_g. One can prove that the Frobenius action commutes with the G-action.

    Let F(x) be the element of G such that F(x) y_i = Frob(y_i). Exercise: The conjugacy class of F(x) is independent of the chose of y_i.

    In the S_n case, this gets really concrete: Let the factors of your squarefree polynomial, in F_q[x], have degrees d_1, d_2, …, d_r with sum d_i = n. Then the cycles of the Frobenius conjugacy class have lengths d_1, d_2, …, d_r.

    We can make the concrete more abstract again by mentioning the following lemma I learned from http://math.ucr.edu/home/baez/week234.html : Let G be a finite group and let T be a set on which G acts freely and without stabilizer. Let H be the group of permutations of T which commute with the G action. Then G and H are isomorphic, but the isomorphism is only natural up to conjugacy.

    So, in this case, take T to be y_1, y_2, …, y_g . Then the Frobenius acts on the y_i by an element of H, and hence gives a natural conjugacy class in G.

  4. And here’s another way to think about this (which I like because it makes a connection with Katz-Sarnak type of questions on L-functions and random matrices): consider the 0-dimensional scheme over F_q given by X_f=Spec(F_q[X]/(f)). Over a fixed algebraic closure of F_q, it is a set of n points, permuted by Frobenius, and the permutation is well-defined up to conjugacy.

    Or: take the 0-th cohomology (with Z_ell or Q_{ell} coefficients) of X_f; this is an n-dimensional vector space, and the action of Frobenius on this cohomology is conjugate to a permutation matrix. Then for instance the number of cycles of the permutation is the multiplicity of the eigenvalue 1 for the characteristic polynomial of this action.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 486 other followers

%d bloggers like this: